poj 1961 Period（KMP）

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

题目大意：给出一个长为n的字符串，求到每个字符之前有多少个字串循环次数大于1

方法： kmp ，求出这个字符串的next数组。在字符串位数是i-next[i]的整数倍是。输出字串循环次数。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>

using namespace std;
int next[1000010];
char str[1000010];

void getnext(char *s, int len)
{
    int i = 0;
    int j = -1;
    next[0] = -1;
    while(i < len)
    {
        if(j == -1 || str[i] == str[j])
            next[++i] = ++j;
        else
            j = next[j];
    }
}
int main()
{
    int n;
    int cas = 0;
    while(~scanf("%d",&n) && n)
    {
        scanf("%s",str);
        getnext(str,n);
        printf("Test case #%d
",++cas);
        for(int i=1;i<=n;i++)
        {
            int d = i - next[i];
            if(next[i] && i % (i-next[i])== 0)
                printf("%d %d
",i, i/(i-next[i]));
        } printf("
");
    }
    return 0;
}