引理：\(s[1,i]\) 具有长度为 \(len\) 的循环节的充要条件是：\(len\ |\ i，s[1,i-len]=s[len+1,i]\)。

代码如下

#include <cstdio>

#include <cstring>

using namespace std;

const int maxn=1e6+10;

char s[maxn];

int n,kase,fail[maxn];

void get_fail(){

	fail[1]=0;

	for(int i=2,j=0;i<=n;i++){

		while(j&&s[i]!=s[j+1])j=fail[j];

		if(s[i]==s[j+1])++j;

		fail[i]=j;

	}

}

void read_and_parse(){

	scanf("%s",s+1);

	get_fail();

}

void solve(){

	for(int i=2;i<=n;i++)

		if(i%(i-fail[i])==0&&i/(i-fail[i])>1)

			printf("%d %d\n",i,i/(i-fail[i]));

	puts("");

}

int main(){

	while(scanf("%d",&n)&&n){

		printf("Test case #%d\n",++kase);

		read_and_parse();

		solve();

	}

	return 0;

}