1961.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"stdio.h"

long next[1000010],len;
long cf[1000010];
char w[1000100];

void get_next()
{
	long i=1,j=0;
	next[1]=0;
	while(i<=len)
	{
		if(j==0||w[i]==w[j])
		{
			i++;j++;
			//if(w[i]!=w[j])
				next[i]=j;
			//else next[i]=next[j];
		}
		else j=next[j];
	}
	return;
}

int main()
{
	int i,t=1;
	while(1)
	{
		scanf("%ld",&len);
		if(len==0)break;
		scanf("%s",&w[1]);

		get_next();

		printf("Test case #%d\n",t++);
		
		cf[1]=1;
		for(i=2;i<=len;i++)
		{
			if(w[next[i]]==w[i]&&next[i]/cf[next[i]]==i-next[i])
			{
				cf[i]=cf[next[i]]+1;
				printf("%ld %ld\n",i,cf[i]);
			}
			else cf[i]=1;
		}
		printf("\n");
			
	}
	return 0;
}