3089794_ac_125ms_2620k.c

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>

char p[400009];
int m, cnt;
int pai[400009], ans[400009];

void pre()
{
	int k, q;

	pai[1] = 0;
	k = 0;
	for(q = 2; q <= m; q++)
	{
		while(k>0&&p[k+1]!=p[q])
			k = pai[k];
		if(p[k+1]==p[q])
			k++;
		pai[q] = k;
	}
}

int main()
{
	int i;

	while(scanf("%s",&p[1])==1)
	{
		m = strlen(&p[1]);
		pre();
		cnt = 0;
		while(m!=0)
		{
			ans[cnt++] = m;
			m = pai[m];
		}
		printf("%d",ans[cnt-1]);
		for(i = cnt-2; i >= 0; i--)
			printf(" %d",ans[i]);
		printf("\n");
	}
	return 1;
}