i      0  1  2  3  4  5  6  7  8  9  10 11
 a[i]    a  a  b  a  a  b  a  a  b  a  a  b
next[i] -1  0  1  0  1  2  3  4  5  6  7  8   

 1 #include <iostream>
 2 #include <stdio.h>
 3 using namespace std;
 4 char a[1000010];
 5 int next[1000010];
 6 int n;
 7 void GetNext()    //获得a数列的next数组
 8 {
 9     int i=0,k=-1;
10     next[0] = -1;
11     while(i<n){
12         if(k==-1){
13             next[i+1] = 0;
14             i++;k++;
15         }
16         else if(a[i]==a[k]){
17             next[i+1] = k+1;
18             i++;k++;
19         }
20         else
21             k = next[k];
22     }
23 }
24 void DisRes(int num)
25 {
26     int j;
27     printf("Test case #%d\n",num);
28     for(int i=0;i<=n;i++){
29         if(next[i]==-1 || next[i]==0)   //next[i]是-1或0的忽略，说明之前没有周期性前缀
30             continue;
31         j = i - next[i];
32         if(i%j==0)  //能整除，说明存在周期性前缀
33             printf("%d %d\n",i,i/j);    //输出这个前缀的长度和周期数
34     }
35     printf("\n");
36 }
37 int main()
38 {
39     int num = 0;
40     while(scanf("%d",&n)!=EOF){
41         if(n==0) break;
42         scanf("%s",a);
43         GetNext();  //获得next[]数组
44         DisRes(++num);  //输出结果
45     }
46     return 0;
47 }