前情提要
本题解重在使大家理解。
本题需要 KMP，相信阅读本篇的大佬都会吧。
没学过也没关系，点这里。这是一篇我喜欢的讲解，不喜勿喷。
分析
看见本题的第一感就是会与 KMP 中的 $next$ 数组有关。
我们通过下面证明可以得出：满足 $i \bmod len = 0$，且 $S[1 \sim i-len] = S[len+1 \sim i]$ 这样的 $len$ 为循环节，其中 $i$ 为 $S$ 字符串中某个前缀的末尾项。
证必要性：
不妨我们先设 $len$ 为字符串 $S[1 \sim i]$ 循环节的长度，我们明显可得：$i \bmod len = 0$，且 $S[1 \sim i-len]=S[len+1 \sim i]$。如：
$S= \texttt{abcabc}$。则 $len=3$，$i=6$。我们可以发现 $i \bmod len=0$。$S[1 \sim i-len]=\texttt{abc}$。$S[len+1 \sim i]=\texttt{abc}$。所以 $S[1 \sim i-len]=S[len+1 \sim i]$。
对于 $S[1 \sim i-len]=S[len+1 \sim i]$ 其实我们也可以这样理解：因为 $S[1 \sim i]$ 是由 $k$ 个长度为 $len$ 的循环元组成，$S[1 \sim i-len]$ 与 $S[len+1 \sim i]$ 均是由 $k - 1$ 个长度为 $len$ 的循环元组成，那么自然可以得出 $S[1 \sim i-len] = S[len+1 \sim i]$。
至于 $i \bmod len = 0$，我相信不用多讲了吧。
证充分性：
这里，我们就可以设 $len$ 能整除 $i$ 且 $S[1 \sim i-len] = S[len+1 \sim i]$。自然，我们可以得出以上两个字符串的长度能整除 $len$。
得出了这个结论我们又可以开始推导：$S[1 \sim len] = S[len + 1 \sim 2 \times len]$，$S[len+1 \sim 2 \times len] = S[2 \times len+1 \sim 3 \times len]$，依次类推，我们可以得出结论 $S[1 \sim i - len]$ 与 $S[len +1 \sim i]$ 均是由 $k$ 个长度为 $len$，也就是 $S[1 \sim len]$ 是 $S[1 \sim i]$ 的循环节。
还是看不懂？
没事看一下图：
注：图中 $len=2,i=8$。
解释一下。本图中：
$S[1 \sim len]= \texttt{ab}$。
$S[len + 1 \sim 2 \times len]= \texttt{ab}$。
$S[2 \times len+1 \sim 3 \times len]= \texttt{ab}$。
好，回到现在，我们已经证了满足能整除 $i$ 且 $S[1 \sim i-len]=S[len+1 \sim i]$ 的 $len$ 一定是循环结，那这又和 $next$ 数组有什么关系呢？
你们看，这 $S[1 \sim i-len]=S[len+1 \sim i]$ 不就是 $S[1 \sim next_i] = S[i-next_i+1 \sim i]$ 吗？
也就是 $i-len=next_i$。
我们要求长度最小的循环节，就需要 $i-len$ 越大！这不就巧了？$next_i$ 刚好符合这样的条件。
那么这道题也就解出来了！
回顾过程
- 求 $next$ 数组。
- 判断 $i-next$ 是否能整除 $i$。
- 若步骤 2 成立，那么 $len \gets i-next_i$，否则没有循环节。
- 重复 2，3。
代码
本人马蜂不好，不喜勿喷。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 100;
string s;
int n, nxt[N], num;//其中的nxt也就是上文的next数组。
int main() {
ios::sync_with_stdio(0);
while (cin >> n && n) {//重复输入
cin >> s; s = " " + s;//我习惯从1开始遍历
nxt[1] = 0;
for (int i = 2, j = 0; i <= n; i++) {
while (j > 0 && s[i] != s[j + 1]) j = nxt[j];
if (s[i] == s[j + 1]) j++;
nxt[i] = j;
}//步骤1：求next数组
cout << "Test case #" << ++num << "\n";
for (int i = 2; i <= n; i++) {
if (i % (i - nxt[i]) == 0 && i / (i - nxt[i]) > 1)//步骤2
cout << i << " " << i / (i - nxt[i]) << endl;//步骤3
}
cout << endl;
}
return 0;
}
The End
注：部分内容来自 lyd 的算法竞赛进阶指南，图片自绘。