题面翻译
对于给定字符串 \(S\) 的每个前缀，我们想知道它是否为周期串（周期串定义为由若干最小循环节拼接而成的字符串），若是，输出前缀长度和循环节数量。
输入格式
多组数据，每组数据第一行一个整数 \(n\)，表示字符串 \(s\) 的长度，若 \(n=0\) 则结束输入。
若 \(n\ne0\)，则第二行一个字符串 \(S\)，如题意。
输出格式
对于第 \(i\) 组输出，第一行一个字符串 Test case #i。
之后若干行一行两个整数，表示如果字符串 \(S\) 的一个前缀是周期串，它的长度和循环节数量（注意这里的循环节是指长度最小的循环节）。
之后再空一行。
样例输入
3
aaa
12
aabaabaabaab
0
样例输出
Test case #1
2 2
3 3
Test case #2
2 2
6 2
9 3
12 4
提示
\(n\leq10^6\)，字符串 \(S\) 均由小写字母构成。
这道题的难点在于如何判断 \(S[1\sim j]\) 是 \(S[1\sim i](j<i)\) 的最小循环节。
首先有一个很明显的结论——\(j\) 能够整除 \(i\)。
其次有一个不是很明显的结论——当 \(j\) 能够整除 \(i\) 且 \(S[1\sim i-j]=S[j+1\sim i]\) 时，\(S[1\sim j]\) 是 \(S[1\sim i](j<i)\) 的最小循环节。
证明
因为 \(j\) 能够整除 \(i\)，所以 \(j\) 也能够整除 \((i-j)\)。
也就是说 \(S[1\sim i-j]\) 和 \(S[j+1\sim i]\) 的长度应当都为 \(j\) 的倍数。
那么分别取两个字符串的前 \(j\) 项，显然也相等。
再取后面 \(j\) 项，显然还是相等。
由于是 \(j\) 的倍数，所以肯定刚好取完。
也就是说这两个字符串以 \(j\) 为间隔错位相等的。
那么很明显，最后整个字符串也自然以 \(j\) 为循环节展开。
题目要求最小循环节，那么就要让 \(S[1\sim i-j]\) 和 \(S[j+1\sim i]\) 的长度最长。
这个东西是不是十分眼熟，它就是 KMP 算法中的核心——\(next\) 数组。
接下来思路是不是就非常清晰了，求出 \(next\) 数组后枚举 \(i\)，判断是否整除且循环节个数大于 \(1\)，如果两个都满足的话输出就行了。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,t;
const int N=1e6+5;
int nxt[N];
char x[N];
void get(char *s){
nxt[1]=0;
int len=strlen(s+1);
for(int i=2,j=0;i<=len;i++){
while(j>0&&s[i]!=s[j+1]) j=nxt[j];
if(s[i]==s[j+1]) j++;
nxt[i]=j;
}
}
signed main()
{
while(scanf("%lld",&n),n){
scanf("%s",x+1);
get(x);
printf("Test case #%lld\n",++t);
for(int i=2;i<=n;i++){
//i为前缀的长度
//(i-nxt[i])为最小循环节的长度
//i/(i-nxt[i])为最小循环节的个数
if(i%(i-nxt[i])==0&&i/(i-nxt[i])>1){
printf("%lld %lld\n",i,i/(i-nxt[i]));
}
}
puts("");
}
return 0;
}