poj2752 Seek the Name, Seek the Fame (串)

题目链接：http://poj.org/problem?id=2752

//pku2752
//题目意思：
//给一个串，找出所有前缀也是后缀的情况
#include<iostream>
#include<cstring>
using namespace std;
char str[400002];
int next[400002];
int result[400002];
int len;
void index()//用KMP算出next[1~len]
{
	int i=0,j=-1;
	next[0]=-1;
	while(i<len)
	{
		if(j==-1||str[i]==str[j])//匹配
		{
			++i;++j;
			next[i]=j;
		}
		else j=next[j];//j往回走
	}
}
int main()
{
	while(gets(str))
	{
		len=strlen(str);
		int i=0,j=len;
		index();
		while(j!=0)
		{
			result[i++]=j;//从大到小记录可行情况
			j=next[j];//j往回走
		}
		int k;
		for(k=i-1;k>=0;k--)
		{
			cout<<result[k];
			if(k>0)cout<<" ";
		}
		cout<<endl;
	}
	return 0;
}