1 /* 2 *  kmp 3 *  利用next[]数组的性质求周期  4 */ 5 #include 
     
       6 #include 
      
        7 #define N 1000005 8  9 int next[N];10 char str[N];11 12 void indexNext() {13     int i, k = 0;14     next[1] = 0;15     for (i=2; str[i]; ++i) {16         while (k && str[k+1]!=str[i]) k = next[k];17         if (str[k+1] == str[i]) ++k;18         next[i] = k;19     }20 }21 22 void solve() {23     int i, j, k;24     indexNext();25     for (i=2; str[i]; ++i) {26         if (!(i%(i-next[i])) && i/(i-next[i])>1) printf ("%d %d\n", i, i/(i-next[i])); 27     }28     puts("");29 }30 31 int main() {32     int n, i, j, k, t = 0;33     str[0] = '#';34     while (scanf("%d", &n), n) {35         scanf ("%s", str+1);36         printf ("Test case #%d\n", ++t);37         solve();38     }39     return 0;40 }