POJ 1961 循环节

和POJ 2406 几乎一样。前者是求 该字符串的最小的循环节。也就是最大的循环次数。后者是求该字符串的每个前缀的循环节的最大循环次数。（如果有的话）。而且必须大于1。才可以输出。就是POJ 2406变形。加一个循环遍历就可以了。当然了。结论仍然是我【记住】的。

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
#define maxn 1000010
int next[maxn];
char str[maxn];

void getNext(char str[]) {
    int len = strlen(str+1);
    next[1] = 0;
    for (int k=0, q=2; q<=len; ++q) {
        while(k>0 && str[k+1]!=str[q])
            k = next[k];
        if (str[k+1] == str[q])
            k++;
        next[q]=k;
    }
}

int main() {
    int len;
    int cnt = 0;
    while(cin >> len && len) {
        cin >> (str+1);
        getNext(str);
        cout << "Test case #" << ++cnt << endl;
        for (int i=2; i<=len; ++i) {
            int temp = i-next[i];
            if (temp != i && i % temp == 0) {
                cout << i << ' ' << (i/temp) << endl;
            }
        }
        cout << endl;
    }
    return 0;
}