pku2752.cpp

来自「内有KMP的模板和pku2406」· C++ 代码 · 共 43 行

////POJ Seek the Name, Seek the Fame
///KMP 

#include <stdio.h>
#include <string.h>
#define MAX  400000
char str[MAX];
int next[MAX], res[MAX];
int len;

void get_next()
{
	int i=0, j=-1;
	next[0] = -1;
	for(;str[i];){
		if(j==-1||str[i]==str[j]){
			i++; j++;
			next[i] = j;
		}else{
			j = next[j];
		}
	}
}

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