pku2752.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 53 行

#include <stdio.h>
#include <string.h>
#define SIZE 1000000

int next[SIZE];
char s[SIZE];
int st[SIZE], top;

void GetNext(char* t,int lt,int* next) 
{ 
	int i = 1,j = 0; 
	next[0] = -1; 
	while(i < lt) 
    {
		if(j < 0 || t[i]==t[j]) 
		{ 
			i++; j++; 
			next[i] = j; 
		} 
		else
		{
			j=next[j];
		}
	}
} 

int main()
{
	int l, i;
	while (scanf("%s", s) != -1)
	{
		l = strlen(s);
		GetNext(s, l, next);

		i = l - 1;
		top = 1;
		st[0] = l;
		i = l;
		while (next[i] != -1 && next[i] != 0)
		{
			st[top++] = next[i];
			i = next[i];
		}
		for (i = top - 1; i >= 0; i--)
		{
			printf("%d ", st[i]);
		}
		printf("\n");
	}
	return 0;
}