POJ 1961 Period

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 #include <climits>
 7 #include <vector>
 8 #include <queue>
 9 #include <cstdlib>
10 #include <string>
11 #include <set>
12 #include <stack>
13 #define LL long long
14 #define pii pair<int,int>
15 #define INF 0x3f3f3f3f
16 using namespace std;
17 const int maxn = 1000010;
18 char str[maxn];
19 int n,fail[maxn],cs = 1;
20 void getFail(){
21     fail[0] = fail[1] = 0;
22     int i;
23     printf("Test case #%d\n",cs++);
24     for(i = 1; str[i]; i++){
25         int j = fail[i];
26         if(i%(i-fail[i]) == 0 && i/(i - fail[i]) > 1)
27             printf("%d %d\n",i,i/(i-fail[i]));
28         while(j && str[i] != str[j]) j = fail[j];
29         fail[i+1] = str[i] == str[j] ? j+1:0;
30     }
31     if(i%(i - fail[i]) == 0 && i/(i - fail[i]) > 1)
32         printf("%d %d\n",i,i/(i - fail[i]));
33 }
34 int main() {
35     bool ok = false;
36     while(scanf("%d",&n),n){
37         if(ok) puts("");
38         ok = true;
39         scanf("%s",str);
40         getFail();
41     }
42     return 0;
43 }