POJ 2406 Power Strings（字符串的最小循环节）

题目链接：http://poj.org/problem?id=2406

题意：确定字符串最多是多少个相同的字串重复连接而成的

思路：关键是找到字符串的最小循环节

code：

 1 #include <cstdio>
 2 #include <cstring>
 3 const int MAXN = 1000005;
 4 char s[MAXN];
 5 int next[MAXN];
 6 void GetNext()
 7 {
 8     int len = strlen(s);
 9     int i = 0;
10     int j = -1;
11     next[0] = -1;
12     while (i < len)
13     {
14         if (-1 == j || s[i] == s[j]) next[++i] = ++j;
15         else j = next[j];
16     }
17 }
18 
19 int main()
20 {
21     while (scanf("%s", s), s[0] != '.')
22     {
23         int len = strlen(s);
24         GetNext();
25         if (len % (len - next[len]) == 0) printf("%d
", len / (len - next[len]));
26         else printf("1
");
27     }
28     return 0;
29 }