POJ 1961 Period KMP算法next数组的应用

题目： http://poj.org/problem?id=1961

很好的题，但是不容易理解。

因为当kmp失配时，i = next[i]，所以错位部分就是i - next[i]，当s[0]...s[i]是一个周期串时，i-next[i]显然就是一个循环节，这时(i+1) % (i-next[i]) == 0,（因为下标是从0开始的，所以i+1表示前i个字符，也就是字符个数），判断上式是否为0就可以判断是否是周期串，如果是周期串时，(i+1) / (i-next[i]) 显然就是重复的次数。

#include <stdio.h>
#include <string.h>
int n, next[1000010];
char s[1000010];
void kmp_init()
{
    int j = -1;
    next[0] = -1;
    for(int i = 1; i < n; i++)
    {
        while(j >= 0 && s[j+1] != s[i])
            j = next[j];
        if(s[j+1] == s[i])
            j++;
        next[i] = j;
    }
}
int main()
{
    int item = 0;
    while(scanf("%d", &n) != EOF && n)
    {
        scanf("%s", s);
        kmp_init();
        printf("Test case #%d
", ++item);
        for(int i = 1; i < n; i++)
        {
            if(next[i] >= 0 && (i+1) % (i-next[i]) == 0)
                printf("%d %d
", i+1, (i+1)/(i-next[i]));
        }
        printf("
");
    }
    return 0;
}