【题意】:给出一个串,求出它重复子串的长度

【题解】:kmp,求出原串的next[]。
               如果len % (len - next[len]) == 0,说明原串是由一个子串连续拼接而成的,且重复子串的长度为 (len / (len - next[len]));

【代码】:
 1 #include "iostream"
 2 #include "cstdio"
 3 #include "cstring"
 4 #include "algorithm"
 5 #include "vector"
 6 #include "queue"
 7 #include "cmath"
 8 #include "string"
 9 #include "cctype"
10 #include "map"
11 #include "iomanip"
12 using namespace std;
13 #define pb push_back
14 #define lc(x) (x << 1)
15 #define rc(x) (x << 1 | 1)
16 #define lowbit(x) (x & (-x))
17 #define ll long long
18 #define maxn 1000050
19 char s[maxn];
20 int next[maxn];
21 void getnext() {
22     int i = 0, j = -1;
23     next[i] = j;
24     int len = strlen(s);
25     while(i < len) {
26         if(j == -1 || s[i] == s[j]) i++, j++, next[i] = j;
27         else j = next[j];
28     }
29 }
30 
31 int main() {
32     while(~scanf("%s", s)) {
33         if(strcmp(s, ".") == 0) break;
34         getnext();
35         int len = strlen(s);
36         if(len % (len - next[len]) == 0) printf("%d\n", len / (len - next[len]));
37         else printf("1\n");
38     }
39     return 0;
40 }
41