题目来源：http://acm.hdu.edu.cn/showproblem.php?pid=1358

题意：

给了一个长度为n的字符串,然后让你找每一个前缀(从第二个字母开始)是否是循环的,如果是就把
当前的位置和循环节的长度输出

思路：

就是 next 数组的使用,令 j=i−next[i] ,如果 i%j==0 就证明存在循环节,循环节的长度为 i/j

ps:数组开小报超时，我佛了HDU牛逼

参考代码：

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
#define end '\n'
#define IOS ios::sync_with_stdio(0)
int nxt[N];
void get_next(string p) {
    int len = p.length();
    int j = 0, k = -1;
    nxt[0] = -1;
    while (j < len)
        if (k == -1 || p[j] == p[k])
            nxt[++j] = ++k;
        else
            k = nxt[k];
}
int main() {
    int n, q = 1;
    string p;
    while (cin >> n && n) {
        cin >> p;
        get_next(p);
        printf("Test case #%d\n", q++);
        for (int i = 1; i <= n; i++) {
            int j = i - nxt[i];
            if (i / j > 1 &&i % j == 0 )
                printf("%d %d\n", i, i / j);
        }
        puts("");
    }
    return 0;
}
/*3 aaa 12 aabaabaabaab 0 Test case #1 2 2 3 3 Test case #2 2 2 6 2 9 3 12 4*/