题目链接: poj 2752
题目大意: 给出字符串，找出所有的前缀和后缀相等的子串
按小到大输出这些子串的长度
解题思路:
如图所示，根据next[ ]前缀的性质左边有颜色部分和右边有颜色部分完全相等
因为左边的红色和右边的红色相等，如果左边的红色和左边的绿色相等，则左边的红色必定与右边的绿色相等
既左红+左蓝+左绿和左绿是我们要求的子串
根据这个规律不断地递推下去，所有的子串都可以求出来
代码:
//Final KMP变形，找出所有字符串的子串的长度，子串满足既是前缀又是后缀(可以重叠)
#include <stdio.h>
#include <string.h>
#define MAX 410000
char ch[MAX];
int Tlen,next[MAX],ans[MAX];
void Get_next() //求字符串的next[]前缀数组
{
int i=0,j=-1;
next[0]=-1;
while(i<Tlen)
{
if(j==-1||ch[i]==ch[j])
{
i++; j++;
next[i]=j;
}
else
j=next[j];
}
}
int main()
{
int i,n;
while(scanf("%s",ch)!=EOF)
{
n=0;
Tlen=strlen(ch);
memset(next,0,sizeof(next));
Get_next();
ans[0]=Tlen; //本身也是
n=0; i=Tlen;
while(next[i]>0) //根据next[]性质求出所有满足题意的长度
{
ans[++n]=next[i];
i=next[i];
}
for(i=n;i>=0;i--)
{
printf("%d",ans[i]);
if(i!=0)
printf(" ");
}
printf("\n");
}
return 0;
}