题意：求两个字符串前缀和后缀的最大相同字符串，并输出其长度。
解题关键：连接起来，kmp解决之。利用Next[len]的性质。 注意该长度 不能超过两个字符串中的任何一个的长度
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<cstdlib> 5 #include<cmath> 6 #include<iostream> 7 #define N 1000002 8 using namespace std; 9 typedef long long ll; 10 int Next[N]; 11 char s[N],t[N]; 12 int slen,tlen; 13 int n,m; 14 int num=0,num1=0,num2=0; 15 void getNext(){ 16 tlen=strlen(t); 17 int i=0,j=-1; 18 Next[0]=-1; 19 while(i<tlen){ 20 if(j==-1||t[i]==t[j]) Next[++i]=++j; 21 else j=Next[j]; 22 } 23 } 24 25 int main(){ 26 while(scanf("%s %s",t,s)!=EOF){ 27 strcat(t,s); 28 getNext(); 29 if(Next[tlen]==0){ 30 printf("0\n"); 31 continue; 32 }else{ 33 int r1=strlen(s),r2=tlen-r1; 34 int tmin=min(r1,r2); 35 if(Next[tlen]>tmin) Next[tlen]=tmin; 36 int t2=tlen-Next[tlen]; 37 printf("%s %d\n",t+t2,Next[tlen]); 38 } 39 40 } 41 return 0; 42 }