Period POJ - 1961

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 
 5 using namespace std;
 6 
 7 #define maxn 1000008
 8 
 9 char s[maxn];
10 int next[maxn];
11 
12 void getNext()
13 {
14     int j, k, i;
15     i = strlen(s);
16 
17     j = 0;
18     k = -1;
19     next[0] = -1;
20     while(j < i)
21     {
22         if(k == -1 || s[j] == s[k])
23         {
24             j++;
25             k++;
26             next[j] = k;
27         }
28         else
29             k = next[k];
30     }
31 }
32 
33 int main()
34 {
35     int q, p = 1;
36     while(scanf("%d", &q), q)
37     {
38         scanf("%s", s);
39 
40         memset(next, 0, sizeof(next));
41         getNext();
42 
43         printf("Test case #%d\n", p++);
44 
45         for(int i = 2; i <= q; i++)
46         {
47             int k = next[i]; // 这个前缀的，前缀和后缀最长的相等长度
48             if(i % (i - k) == 0 && i / (i - k) != 1)  // 满足循环节……循环 输出
49                 printf("%d %d\n", i, i / (i - k));
50         }
51         puts("");
52     }
53     return 0;
54 }