KMP算法和周期性字符串.
i-next[i] 为最小循环元长度,i/(i-next[i])为最大循环次数.
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
const int INF = 1e9;
int Next[1000010];
char p[1000010];
void kmp_pre(char x[],int m,int next[]){
int i,j;
j=next[0]=-1;
i=0;
while(i<m){
while(-1!=j&&x[i]!=x[j]) j=next[j];
next[++i]=++j;
}
}
int main() {
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int kase=0;
int n;
while(cin>>n&&n){
scanf("%s",p);
kmp_pre(p,n,Next);
int i=n;
printf("Test case #%d\n",++kase);
for(int i=2;i<=n;++i){
if(i/(i-Next[i])>1&&i%(i-Next[i])==0){
printf("%d %d\n",i,i/(i-Next[i]));
}
}
printf("\n");
}
return 0;
}