POJ2406 kmp算法next数组-串的最小循环节/循环周期

题目大意：问给出的字符串最多由多少个子串相乘得来的。

思路：利用next数组的含义来解。

1.一个串的最小循环节长度：len - next[len]

2.若len%(len-next[len]) == 0, 则这个字符串的最小周期为len/(len-next[len])。一定要注意前提是 len % (len - next[len]) == 0,否则不存在循环周期。

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define mem(a, b) memset(a, b, sizeof(a))
 4 const int MAXN = 1000000 + 10;
 5 
 6 char s[MAXN];
 7 int s_len, next[MAXN];
 8 
 9 void get_next()
10 {
11     next[0] = -1;
12     int j = 0, k = -1;
13     s_len = strlen(s);
14     while(j < s_len)
15     {
16         if(k == -1 || s[j] == s[k])
17         {
18             j ++, k ++;
19             next[j] = k;
20         }
21         else
22             k = next[k];
23     }
24 }
25 
26 int main()
27 {
28     while(scanf("%s", s) != EOF)
29     {
30         if(strcmp(s, ".") == 0)
31             break;
32         get_next();
33         if(s_len % (s_len - next[s_len]) == 0)
34             printf("%d
", s_len / (s_len - next[s_len]));
35         else
36             printf("1
");
37     }
38     return 0;
39 }

POJ2406