AcWing
141. 周期
KMP. next[i]的含义：长度为i的字符串中，前缀和后缀重合部分的长度。T = i - next[i]表示长度为i的字符串的最短周期长度(如果存在，即，字符长度能被这个周期整除，且长度不等于周期)。
#include <bits/stdc++.h>
using namespace std;
int n;
const int N = 1000010;
char str[N];
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int T = 1;
while(1){
cin >> n;
if(!n) break;
cin >> str + 1;
// ----------next数组，模板----------
int ne[N];
for(int i = 2, j = 0; i <= n; i++){
while(j && str[i] != str[j + 1]) j = ne[j];
if(str[i] == str[j + 1]) j++;
ne[i] = j;
}
// ---------------------------------
cout << "Test case #" << T++ << '\n';
for(int i = 2; i <= n; i++){
int t = i - ne[i];
if(i % t == 0 && i != t){
cout << i << ' ' << i / t << '\n';
}
}
cout << '\n';
}
return 0;
}