Power Strings(KMP)

题意：计算一个串中重复因子出现的最多次数，即最多的循环节数。

 1 #include <stdio.h>
 2 #include <string.h>
 3 const int N=1000010;
 4 char str[N];
 5 int next[N];
 6 
 7 int get_next(char *s)
 8 {
 9     int j = 0,k = -1;
10     int len=strlen(s);
11     next[0]=-1;
12     while(j<len)
13     {
14         if(k==-1||s[k]==s[j])
15             next[++j]=++k;   
16         else
17             k = next[k];
18     }
19     j = len-k;
20     if (len%j==0)
21         return len/j;
22     else
23         return 1;
24 }
25 int main()
26 {
27     while(~scanf("%s",str))
28     {
29         if(str[0]=='.')
30             break;
31         printf("%d
",get_next(str));
32     }
33     return 0;
34 }

View Code