kmp 与最小循环节

题目:
一个字符串的前缀是从第一个字符开始的连续若干个字符，例如 abaab 共有 5 个前缀，分别是 a，ab，aba，abaa，abaab。

我们希望知道一个 N 位字符串 S 的前缀是否具有循环节。

换言之，对于每一个从头开始的长度为 i（i>1）的前缀，是否由重复出现的子串 A 组成，即 AAA…A （A 重复出现 K 次,K>1）。

如果存在，请找出最短的循环节对应的 K 值（也就是这个前缀串的所有可能重复节中，最大的 K 值）。

输入格式
输入包括多组测试数据，每组测试数据包括两行。

第一行输入字符串 S 的长度 N。

第二行输入字符串 S。

输入数据以只包括一个 0 的行作为结尾。

输出格式
对于每组测试数据，第一行输出 Test case # 和测试数据的编号。

接下来的每一行，输出具有循环节的前缀的长度 i 和其对应 K，中间用一个空格隔开。

前缀长度需要升序排列。

在每组测试数据的最后输出一个空行。

数据范围
2≤N≤1000000

这道题一开始用的kmp+hash，较麻烦，还有些性质每挖出来。
先用kmp算法预处理ne数组。
如果这个字符串有最小循环节的话，T = n - ne[n];
且 T 是最小的。
所有我们看这个字符串的n能不能整除T即可。能的话就是，不能就不是。
若能整除还要排除 ne[n] = 0的情况。
我一开始用hash 是没有挖掘出整除既是的性质。我还去判断了前T个字符和后T个字符是否相等。
现在想来发现这俩事情是等价的，所以麻烦了。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1000010;

int n;
char s[N];
int ne[N];

int main()
{
    int T = 1;
    while (scanf("%d", &n), n)
    {
        scanf("%s", s + 1);
        for (int i = 2, j = 0; i <= n; i ++ )
        {
            while (j && s[i] != s[j + 1]) j = ne[j];
            if (s[i] == s[j + 1]) j ++ ;
            ne[i] = j;
        }

        printf("Test case #%d\n", T ++ );
        for (int i = 1; i <= n; i ++ )
        {
            int t = i - ne[i];
            if (i % t == 0 && i / t > 1)
                printf("%d %d\n", i, i / t);
        }
        puts("");
    }

    return 0;
}