pku 2752 //kmp運用

#include <stdio.h>
#include <string.h>
char s[400003];
int next[400003];
int a[400003];
int len;

void GetNext()
{
	int i,j;
	s[0] = '#';
	len = strlen(s);
	next[1] = 0;
	j=0;
	int temp = 0;
	for(i=2;i<=len;i++)
	{
		while(j>0 && s[j+1]!=s[i])
			j = next[j];
		if(s[j+1] == s[i]){
			j++;
		}
		next[i] = j;
	}
}

void Print()
{
	int temp = len - 1;
	int num = 0;
	a[num++] = len - 1;
	while(next[temp])
	{
		a[num++] = next[temp];
		temp = next[temp];
	}
	for(int i=num-1;i>0;i--) printf("%d ",a[i]);
	printf("%d\n",a[0]);
}

int main()
{
	int n;
	while(scanf("%s",s+1)!=EOF)
	{
		getchar();
		GetNext();
		Print();
	}
	return 0;
}
           

轉載于:https://www.cnblogs.com/cykun/archive/2011/02/20/1958974.html