POJ 2406 Power Strings

给定一个串，求其一个重复不重叠子串重复次数的最大值（循环节了解一下）

就是对KMP匹配的理解

比较推荐这道HDU-3746

另外还有hdu3374 考察了循环节的同时，还有字符串的最大最小表示大牛题解

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 using namespace std;
 5 
 6 const int maxn = 1e6 + 10;
 7 char pattern[maxn];
 8 int nxt[maxn];
 9 
10 void getnext() {
11     int n = strlen(pattern);
12     for (int i = 1; i < n; i++) {
13         int j = i;
14         while (j > 0) {
15             j = nxt[j];
16             if (pattern[j] == pattern[i]) {
17                 nxt[i + 1] = j + 1;
18                 break;
19             }
20         }
21     }
22 }
23 
24 int main(int argc, const char * argv[]) {
25     while (~scanf("%s", pattern)) {
26         if (pattern[0] == '.') break;
27         memset(nxt, 0, sizeof(nxt));
28         getnext();
29         int len = strlen(pattern);
30         if (len % (len - nxt[len]) == 0) {
31             printf("%d
", len / (len - nxt[len]));
32         } else {
33             puts("1");
34         }
35     }
36     return 0;
37 }