POJ 2406 Power Strings（KMP）

 1 #include <cstdio>
 2 #include <algorithm>
 3 #include <iostream>
 4 #include <cstring>
 5 using namespace std;
 6 
 7 const int MAXN = 1000010;
 8 
 9 void getFail(char *P, int m, int f[]) {
10     f[0] = f[1] = 0;
11     for(int i = 1; i < m; ++i) {
12         int j = f[i];
13         while(j && P[i] != P[j]) j = f[j];
14         f[i + 1] = (P[i] == P[j] ? j + 1 : 0);
15     }
16 }
17 
18 char s[MAXN];
19 int fail[MAXN], n;
20 
21 int main() {
22     while(scanf("%s", s) != EOF) {
23         if(*s == ‘.‘) break;
24         n = strlen(s);
25         getFail(s, n, fail);
26         if(n % (n - fail[n]) == 0) printf("%d\n", n / (n - fail[n]));
27         else puts("1");
28     }
29 }