kmp算法的应用，和poj 2406类似

如果长度为l的前缀是由字符串重复构成的，则next[l] != 0，且此时构成前缀的重复子串的最小长度为l - next[l]，l % (l - next[l]) = 0，最大重复次数为l / (l - next[l])。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 1000010
char str[N];
int next[N], len;

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


int main()
{
    int count = 1;
    int i;
    while (scanf("%d", &len) && len)
    {
        memset(str, 0, N);
        scanf("%s", str);
        get_next();
        printf("Test case #%d\n", count++);
        for (i = 2; i <= len; i++)
            if (next[i] && i % (i - next[i]) == 0)
                printf("%d %d\n", i, i / (i - next[i]));
        printf("\n");
    }
    return 0;
}