题意
给定字符串，找到每个前缀的最大循环节的个数，即循环周期，如果大于1的话就输出下标和周期数（循环节）
解题思路
KMP就可以非常轻松的解决问题，首先提到一个next数组的性质，对于当前的前缀a[j]，如果j % (j - next[j]) == 0则j - next[j]即为最小周期长度，而周期数就是j / (j - next[i])，至于为什么j - next[j]为最小周期长度呢，请听我慢慢徐来，先看下面的示意图
通过看这幅图大家或许也能看懂，我就稍微讲述一下，我们当前失配了j点，然后我们需要调到next[j]，那我们知道1子串和2子串必须是相等的，就是公共后缀子串。
所以从j开始往0走的方向上，第一个长度为k和第二个长度为k的字符串是相等的。又因为w == w（因为1==2并且长度为k的后缀字符串也是相等的），所以w字符串的后缀长度为k的字符串等于以j和next[j]为结尾长度为k的后缀字符串。
以此类推，只要我们的j % (j - next[j])为0就可以保证从j往前走有j / (j - next[j])个长度为j - next[j]的字符串相等。
如此，证明完毕，如果不懂滴，可以留言。
代码
#include <iostream> #include <fstream> #include <string> #include <map> #include <set> #include <algorithm> using namespace std; typedef long long LL; constexpr int MAXN = 2e6 + 5; constexpr int MAXM = 4e4 + 5; constexpr int mod = 20071027; string b; int n,nexts[MAXN]; void getNext(string a) { int k = nexts[0] = -1; int j = 0; while(j < a.length()) { if(k == -1 || a[j] == a[k]) { j ++; k ++; nexts[j] = k; } else { k = nexts[k]; } } } int main() { ios::sync_with_stdio(false); //ifstream in("input.txt"); //cin.rdbuf(in.rdbuf()); int cas = 1; while(cin >> n && n) { cin >> b; getNext(b); cout << "Test case #" << cas ++ << endl; for(int i = 0; i <= n; i ++) { if(i && i % (i - nexts[i]) == 0 && i / (i - nexts[i]) > 1) { cout << i << " " << i / (i - nexts[i]) << endl; } } cout << endl; } return 0; }