Period(KMP)

Period
Time Limit: 3000MS
 
Memory Limit: 30000K
Total Submissions: 11807
 
Accepted: 5501
Description
For each prefix of a given string S with N characters (each character has an ASCII code between 97 and 126, inclusive), we want to know whether the prefix is a periodic string. That is, for each i (2 <= i <= N) we want to know the largest K > 1 (if there is one) such that the prefix of S with length i can be written as A
K ,that is A concatenated K times, for some string A. Of course, we also want to know the period K.
Input
The input consists of several test cases. Each test case consists of two lines. The first one contains N (2 <= N <= 1 000 000) – the size of the string S.The second line contains the string S. The input file ends with a line, having the 
number zero on it.
Output
For each test case, output "Test case #"and the consecutive test case number on a single line; then, for each prefix with length i that has a period K > 1, output the prefix size i and the period K separated by a single space; the prefix sizes must be in increasing order. Print a blank line after each test case.
Sample Input

3
aaa
12
aabaabaabaab
0

Sample Output

Test case #1
2 2
3 3

Test case #2
2 2
6 2
9 3
12 4

Source
Southeastern Europe 2004
제목:
여러 케이스, 0 입력 완료.각 케이스마다 N (2 <= N <= 100000) 이 있으며, n 길이의 문자열이 있음을 의미하며, 그 다음에 문자열을 제공합니다.i는 문자열의 접두사 길이를 나타냅니다. 2에서 N까지 각 접두사 서브열의 최대 반복 주기 K(K > 1)를 구하고 i의 오름차순으로 출력합니다.
 
생각:
KMP의 next 값을 사용하여 이전 문제와 유사합니다.주의해야 할 것은 정리를 판단하고 주기가 1보다 크면 출력하고 외순환은 i=2부터 시작한다는 것이다.문자열 배열은 0에서 시작되기 때문에 순환은 n 길이까지 순환해야 합니다.
 
    AC:

#include<stdio.h>
int n,next[1000005];
char str[1000005];

void get_next()
{
    int i = 0,j = -1;
    next[0] = -1;
    while(i < n)
    {
        if(j == -1 || str[i] == str[j]) next[++i] = ++j;
        else                            j = next[j];
    }
}

int main()
{
    int test = 0;
    while(scanf("%d",&n)!=EOF && n)
    {
        int per;
        test++;
        for(int i = 0;i < n;i++)
            scanf(" %c",&str[i]);
        get_next();
        per = n - next[n];
        printf("Test case #%d
",test);
        for(int i = 2;i <= n;i++)   // n
            if(!(i % (i - next[i])) && (i / (i - next[i]) != 1))
            printf("%d %d
",i,i / (i - next[i]));
        printf("
");
    }
    return 0;
}