poj 2752

题意：给你一个串，如果这个串存在一个长度为n的前缀串，和长度为n的后缀串，并且这两个串相等，则输出他们的长度n。求出所有的长度n。

 思路：KMP中的get_next()。对前缀函数next[]又有了进一步的理解，str[1]~~str[next[len]]中的内容一定能与str[1+len-next[len]]~~str[len]匹配（图1）。然后呢我们循环地利用next，由于next的性质，即在图2中若左红串与左绿串匹配，则左红串比与右绿串匹配，因为图1的左红串与右红串是完全相等的。可以保证，每一次得出的字串都能匹配到最后一个字母，也就是得到一个前缀等于后缀。只不过这个字符串的长度在不断地减小罢了。

 

 

#include<iostream>
using namespace std;
const int Max = 400005;

char str[Max];
int len, next[Max], ans[Max];

void get_next()
{
	int j=1,k=0;
	next[0]=-1;
	next[1]=0;
	while (j<len)
	{
		if (str[j]==str[k])
		{
			next[j+1]=k+1;
			j++;
			k++;
		} 
		else if(k==0)
		{
			next[j+1]=0;
			j++;
		}
		else
			k=next[k];
	}
}

int main()
{
    while(scanf("%s",str)!= EOF)
	{
        len = strlen(str);
        get_next();
        ans[0] = len;
        int n = 0, i = len;
        while(next[i]> 0)
		{
			n++;
            ans[n] = next[i];
            i = next[i];
        }
        for(i = n; i >= 0; i--)
            printf("%d ", ans[i]);
        printf("\n");
    }
    return 0;
}