Period

Problem Description

For each prefix of a given string S with N characters (each character has an ASCII code between 97 and 126, inclusive), we want to know whether the prefix is a periodic string. That is, for each i (2 <= i <= N) we want to know the largest K > 1 (if there is one) such that the prefix of S with length i can be written as AK , that is A concatenated K times, for some string A. Of course, we also want to know the period K.

Input

The input file consists of several test cases. Each test case consists of two lines. The first one contains N (2 <= N <= 1 000 000) – the size of the string S. The second line contains the string S. The input file ends with a line, having the number zero on it.

Output

For each test case, output “Test case #” and the consecutive test case number on a single line; then, for each prefix with length i that has a period K > 1, output the prefix size i and the period K separated by a single space; the prefix sizes must be in increasing order. Print a blank line after each test case.

Sample Input

3

aaa

12

aabaabaabaab

0

Sample Output

Test case #1

2 2

3 3

Test case #2

2 2

6 2

9 3

12 4

题意描述：

求长度为n的字符串，长度最少为2能够形成循环的长度及循环数；如样例中：aabaabaabaab

当长度为2时字符串为aa构成了循环循环节为a循环数2，输出2  2，当长度为3,4,5时都构不成循环，长度为6时字符串为aabaab构成循环，循环节为aab循环数为2，输出6  2，当长度为9时字符串为aabaabaab构成循环，循环节为aab循环数为3，输出9  3……

解题思路：

求出next[ ]数组利用循环判断长度是否能构成循环，长度为i+1若是循环i+1-next[i]为循环节长度，若长度是循环节的倍数时就构成了循环（注意next[i]=0情况时不成立）；

#include<stdio.h>
#include<string.h>
int next[1000010];
void get_next(char s[])
{
	int i,j,len;
	len=strlen(s);
	j=0;
	i=1;
	next[0]=0;
	while(i<len)
	{
		if(j==0&&s[i]!=s[j])
		{
			next[i]=0;
			i++;
		}
		else if(j>0&&s[i]!=s[j])
			j=next[j-1];
		else
		{
			next[i]=j+1;
			i++;
			j++;
		}
	}
}
int main()
{
	int n,t,i;
	char a[1000010];
	t=0;
	while(scanf("%d",&n))
	{
		getchar();
		if(n==0)
			break;
		t++;
		for(i=0;i<n;i++)
			scanf("%c",&a[i]);
		
		printf("Test case #%d\n",t);
		
		get_next(a);
		for(i=1;i<n;i++)
		{
			if((i+1)%(i+1-next[i])==0&&next[i]!=0)//判断是否构成循环 
				printf("%d %d\n",i+1,(i+1)/(i+1-next[i]));
		}
		printf("\n");
	}
	return 0;
}