题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4763
题意：给出一个字符串，问能不能在该串的前中后部找到相同的子串，输出最长的字串的长度。
分析：kmp的next[]数组应用。
next[i]=k表示在位置i之前有k个字符与字符串前k个字符相同，利用这个性质，先求出next[]数组，注意next[len]也要求出来，next[i]就表示字符串的后部与前部相同的长度，这样就只需找有没有中部就可以了。在next[i]到len-next[i]之间找有没有和next[i]相同的值就行了，找到就表示有中部，否则没有,这时i=next[i]，然后继续找有没有中部，一直到next[i]==0为止。
之前的做法是错的，因为题目要求前缀，中缀，后缀不能出现重叠，之前的做法会导致3个错误：
1.可能会导致求出来的前缀和中缀重叠导致错误；
2.在next[i]到len-next[i]中间可能出现长度与前缀相同但是字符不一样的字串，比如：aaaaabbbbaaaa，这样用之前的做法会得出错误的答案；
3.如果前缀和中缀是连续的，那么next[len]就有可能是前缀和中缀的总长度和了，这样也会错误。
所以不能仅仅依靠next[]数组来求解
正确的做法是：
在next[i]到len-next[i]之间用kmp匹配前缀，如果匹配成功，则说明能找到中部，否则不能，i=next[i]然后继续查找中部，直到next[i]==0即可.
根据next[]数组的性质，循环的次数不超过3次，因为如果后部和前部不相同的话，next[i]==0，这样很快就可以跳出循环了。
还可以加个优化：前中后部字串的长度最多为len/3，如果next[i]>len/3的话就可以直接跳过查找中部，进入下一次循环了。但是优化不大，因为循环次数非常少。
AC代码：
1 #include<cstdio> 2 #include<cstring> 3 const int N=1000000+5; 4 int next[N]; 5 char s[N],c[N],d[N]; 6 void get_next(char s[]) 7 { 8 int len=strlen(s); 9 int i=0; 10 int j=-1; 11 next[0]=-1; 12 while(i<=len) //注意要== 13 { 14 if(j==-1||s[i]==s[j]) 15 { 16 i++; 17 j++; 18 next[i]=j; 19 } 20 else 21 j=next[j]; 22 } 23 } 24 int kmp(char t[],char s[]) 25 { 26 int i,j,k,m,n; 27 m=strlen(s); 28 n=strlen(t); 29 i=j=k=0; 30 while(i<m&&j<n) 31 { 32 if(j==-1 || t[j]==s[i]) 33 { 34 i++; 35 j++; 36 } 37 else 38 j=next[j]; 39 } 40 if(j>=n) 41 return 1; 42 else 43 return 0; 44 } 45 int main() 46 { 47 int t,j,k; 48 scanf("%d",&t); 49 while(t--) 50 { 51 scanf("%s",s); 52 get_next(s); 53 int len=strlen(s); 54 int i=next[len]; 55 int flag=0; 56 while(i>0) 57 { 58 while(i>len/3) 59 i=next[i]; 60 if(i<=0) 61 break; 62 /******************************** 63 错误解法： 64 for(j=i;j<=len-i;j++) //找中部 65 if(next[j]==i) 66 { 67 flag=1; 68 break; 69 } 70 ********************************/ 71 for(k=0,j=0;j<i;j++) 72 c[k++]=s[j]; 73 c[k]='\0'; 74 for(k=0;j<len-i;j++) 75 d[k++]=s[j]; 76 d[k]='\0'; 77 flag=kmp(c,d); 78 if(flag==1) //找到了 79 break; 80 else 81 i=next[i]; //找不到，循环继续 82 } 83 if(flag) 84 printf("%d\n",i); 85 else 86 printf("0\n"); 87 } 88 return 0; 89 }