1 #include <cstdio> 2 #include <cstring> 3  4 const int maxn = 1000000 + 10; 5 char p[maxn]; 6 int n, next[maxn]; 7  8 void get_next() 9 {10     int k = -1, j = 0;11     next[0] = -1;12     while(j < n)13     {14         if(k == -1 || p[k] == p[j])15         {16             k++;17             j++;18             next[j] = k;19         }20         else k = next[k];21     }22 }23 24 int main(void)25 {26     //freopen("1358in.txt", "r", stdin);27     int kase = 0;28     while(scanf("%d", &n) == 1 && n)29     {30         memset(next, 0, sizeof(next));31         scanf("%s", p);32         getchar();33         get_next();34         35         printf("Test case #%d\n", ++kase);36         for(int i = 2; i <= n; ++i)37         {38             if(next[i] == 0) continue;39             int cir = i - next[i];40             if(i % cir == 0)41                 printf("%d %d\n", i, i / cir);42         }43         puts("");44     }45 46     return 0;47 }