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;
}