题目链接：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代码：
#include<cstdio>
#include<cstring>
const int N=+;
int next[N];
char s[N],c[N],d[N];
void get_next(char s[])
{
int len=strlen(s);
int i=;
int j=-;
next[]=-;
while(i<=len) //注意要==
{
if(j==-||s[i]==s[j])
{
i++;
j++;
next[i]=j;
}
else
j=next[j];
}
}
int kmp(char t[],char s[])
{
int i,j,k,m,n;
m=strlen(s);
n=strlen(t);
i=j=k=;
while(i<m&&j<n)
{
if(j==- || t[j]==s[i])
{
i++;
j++;
}
else
j=next[j];
}
if(j>=n)
return ;
else
return ;
}
int main()
{
int t,j,k;
scanf("%d",&t);
while(t--)
{
scanf("%s",s);
get_next(s);
int len=strlen(s);
int i=next[len];
int flag=;
while(i>)
{
while(i>len/)
i=next[i];
if(i<=)
break;
/********************************
错误解法：
for(j=i;j<=len-i;j++) //找中部
if(next[j]==i)
{
flag=1;
break;
}
********************************/
for(k=,j=;j<i;j++)
c[k++]=s[j];
c[k]='\0';
for(k=;j<len-i;j++)
d[k++]=s[j];
d[k]='\0';
flag=kmp(c,d);
if(flag==) //找到了
break;
else
i=next[i]; //找不到，循环继续
}
if(flag)
printf("%d\n",i);
else
printf("0\n");
}
return ;
}