POJ_1961

#include<stdio.h>

int next[1000005];
int get_next(int n,char str[]){
	int i=0,j=-1;
	next[0]=-1;
	//当循环到没有正确匹配的str时都令j=next[j]
	//即上一次匹配到的最近 正确的 j 的下一个
	//KMP算法，这样可以减少消耗 
	while(i<n){
		if(j==-1||str[i]==str[j]){
			i++;
			j++;
			next[i]=j;
		}else{
			j=next[j];
		}
	}
}
int main(){
	int i,length,k=1;
	int temp;
	char str[1000005];
	int count=1;
	while(scanf("%d",&length)&&length){
		scanf("%s",str);
		get_next(length,str);
		printf("Test case #%d\n",count);
		count++;
		for(i=1;i<=length;i++){
			temp=i-next[i];
			//temp为最短循环节的长度
			if(i%temp==0&&i/temp>1)
				printf("%d %d\n",i,i/temp);
			//i%temp==0 是因为最小循环节需要被字符串长度整除
			//同时 需要被整除 
		}
		printf("\n");
	}
	return 0; 
}