学步园

求一个字符串的最长后缀出现在一个字符串的前缀

KMP算法，主要是求next[]函数；

#include<stdio.h>
#include<string.h>
char s1[50002],s2[50002];
int next[50002];
void get()
{
    int len=strlen(s1);
    int j,i;
    j=-1;i=0;next[0]=-1;
    while(i!=len)
    {
        if(j==-1||s1[i]==s1[j])
        {
            next[++i]=++j;
        }
        else j=next[j];
    }
}
int KMP()  
{  
    int i,j;  
    int len2;  
    j=0;i=0;   
    len2=strlen(s2);  
    while(i!=len2)//以i之后的为后缀与s1的前缀比较  
    {  
        if(s2[i]==s1[j])//匹配成功  
        {  
            i++;j++;  
        }  
        else  //匹配不成功
        {  
            j=next[j];
            if(j==-1){j=0;i++;}//只有next[0]=-1,所以j=0；
        }  
    }    
    return j;  
}  

int main()
{
    int i,j;
    while(scanf("%s",s1)!=-1)
    {
        scanf("%s",s2);
        get();
        i=KMP();
        if(i<=0)
            puts("0");
        else 
        {
            for(j=0;j<i;j++)
            {
                printf("%c",s1[j]);
            }
            printf(" %d\n",i);
        }
    }
    return 0;
}