HDU 2594 Simpsons’ Hidden Talents【KMP】

题意： 给你两个字符串，让你找出第一个字符串的头部和第二个字符串尾部重合的部分，并尽可能的长，例如 aasdfs bdevaa 答案为 aa 2

分析： 利用 KMP 算法得到的 next 函数的特点，把两字符串连到一起，找出头部和尾部重合的部分。

#include<stdio.h>
#include<string.h>
char s1[50005];
char s2[50005];
int next[100010];
int len1,len2,len;
void get()
{
    int i=0,j=-1;
    next[0]=-1;
    while(i<len)
    {
        if(j==-1||s1[i]==s1[j])
            next[++i]=++j;
        else j=next[j];
    }
}
int main()
{
    int i,k;
    while(scanf("%s%s",s1,s2)!=EOF)
    {
        len1=strlen(s1);
        len2=strlen(s2);
        len=len1+len2;
        strcat(s1,s2);
        get();
        k=len;
        while(next[k]>len1||next[k]>len2)
            k=next[k];
        if(next[k]==0)
            printf("0\n");
        else
        {
            for(i=0;i<next[k];i++)
            printf("%c",s1[i]);
            printf(" %d\n",next[k]);
        }

    }
    return 0;
}