首页 > 代码库 > poj 2406 Power Strings(kmp循环节)

poj 2406 Power Strings(kmp循环节)

题目链接:http://poj.org/problem?id=2406

题目大意:如果n%(n-next[n])==0,则存在重复连续子串,长度为n-next[n]。

例如:      a    b    a    b    a    b

next:-1   0    0    1    2    3    4

next[n]==4,代表着,前缀abab与后缀abab相等的最长长度,这说明,ab这两个字母为一个循环节,长度=n-next[n];

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 int next[1000005],len; 6 char str[1000005]; 7  8 int get_next() 9 {10     int i=0,j=-1;11     next[0]=-1;12     while (i<len)13     {14         if (j==-1||str[i]==str[j])15         {16             i++;17             j++;18             next[i]=j;19         }20         else21             j=next[j];22     }23 }24 25 int main ()26 {27     while (scanf("%s",str)!=EOF)28     {29         if (strcmp(str,".")==0)30             break;31         len=strlen(str);32         get_next();33         if (len%(len-next[len])==0)34             printf("%d\n",len/(len-next[len]));35         else36             printf("1\n");37     }38     return 0;39 }