学步园

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

#include<iostream>
#include<cstdio>
using namespace std;
char s[400005];
int next[400005],a[400005];
void getnext(char *p,int *next){
	int len=strlen(p);
	next[0]=-1;
	int i=0,k=-1;
	while(i<len){
		if(k==-1 || p[i]==p[k]){
			i++;
			k++;
			next[i]=k;
		}
		else
			k=next[k];
	}
}
int main(){
	while(scanf("%s",s)!=EOF){
		getnext(s,next);
		int len=strlen(s),i,k=0;
		i=len;
		a[0]=len;
		while(next[i]>0){
			
			i=next[i];
			a[++k]=i;
		}
		for(int j=k;j>=0;--j){
			printf("%d",a[j]);
			if(j)
				printf(" ");
		}
		printf("\n");
	}
}

这道题目要求既是前缀字符串又是后缀字符串的所有可能的长度，正好运用了KMP算法里面next数组的意义，要保证结果是针对整个字符串的，所以在next数组中从后往前扫描即可，因为，next数组中，越往后，数字就越大，并且表示的是后缀和前缀相同的最大长度，所以所得到的结果顺序是反的，要求从小到大输出，逆序输出就可以了。