【题意】:给出一个串,求出它重复子串的长度
【题解】: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