1 // File Name: getnext.cpp 2 // Author: darkdream 3 // Created Time: 2014年09月09日 星期二 22时35分02秒 4  5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque>10 #include<stack>11 #include<bitset>12 #include<algorithm>13 #include<functional>14 #include<numeric>15 #include<utility>16 #include<sstream>17 #include<iostream>18 #include<iomanip>19 #include<cstdio>20 #include<cmath>21 #include<cstdlib>22 #include<cstring>23 #include<ctime>24 #define LL long long25 26 using namespace std;27 char str[1000004];28 int next[1000005];29 void getnext()30 {31     int len = strlen(str);32     next[0] = -1; 33     int k = -1;34     int j = 0 ;35     int sum = 0 ; 36     while(j <= len - 1)37     {38         if(k == -1 || str[j] == str[k])39         {40             ++j; 41             ++k;42             next[j] = k ;43         }44         else {45             k = next[k];46         }47     }48 /*    for(int i = 0 ;i <= len; i ++)49         printf("%d ",next[i]);50     printf("\n");*/51     for(int i = 2;i <=len; i ++)52     {53         int t = (i - next[i]);54         if(i % t == 0 && i /t !=  1)55         {56            printf("%d %d\n",i,i/t);    57         }58     }59 60 }61 int main(){62     int n ;63     int t = 0  ;64     while(scanf("%d",&n) != EOF,n)65     {66              t++ ;67              scanf("%s",str);68              printf("Test case #%d\n",t);69              getnext();70              printf("\n");    71     }72     return 0;73 }