给一个字符串，求这个字符串的每个前缀（包括本身）能否由k个子串组成（K>1）．

就是对 KMP 算法中 next 数组的理解，我们知道，用 KMP 算法时，当遇到不匹配的话，会根据 next 数组来计算应该匹配哪个地方，比如在模板 j 这个地方不匹配时，会看 next[j] 这个地方是否匹配，那么对于 j - next[j] ，匹配的位置减去next[j]的位置之差，如果 j % (j - next[j]) == 0，就说明是由长度为j-next[j]的子串组成，子串个数为 j / (j - next[j])．

链接：http://acm.hdu.edu.cn/showproblem.php?pid=1358

#include <bits/stdc++.h>
using namespace std;
const int N = (int) 1e6 + 10;
char s[N];
int nex[N];
int main()
{
    int cas = 1, n;
    while (~scanf("%d", &n) && n) {
        scanf("%s", s);
        int i = 0, j = -1;
        nex[0] = -1;
        while (i < n) {
            if (j == -1 || s[i] == s[j]) {
                nex[++i] = ++j;
            } else {
                j = nex[j];
            }
        }
        printf("Test case #%d\n", cas++);
        for (int i = 0; i <= n; i++) {
            if (nex[i] == -1 || !nex[i])
                continue;
            j = i - nex[i];
            if (i % j == 0)
                printf("%d %d\n", i, i / j);
        }
        printf("\n");
    }
    return 0;
}