<>

题目大意：

给出一个字符串，求其字串在该字符串中循环的最大周期。

解题分析：

length=len-Next[len],len为该字符串的最小循环节，如果len%length==0,那么周期就为len/lenght,如果不能整除，则说明该字符串的字串不具有周期性，输出1。

 KMP最小循环节的证明 

#include 
     
      #include 
      
       const int maxn = 1000000 + 100;char str[maxn];int Next[maxn];void get_next(){    int j = 0, k = -1;    Next[0] = -1;    while (str[j])    {        if (k == -1 || str[j] == str[k])            Next[++j] = ++k;        else            k = Next[k];    }}int main(){    while (scanf("%s", &str) != EOF)    {        if (str[0] == '.')break;        get_next();        int len = strlen(str);        int length = len - Next[len];        //最小循环节,注意，要弄清楚循环节的含义                if (len%length == 0)        {            printf("%d\n", len / length);        }        else            printf("1\n");    }    return 0;}
      
     

 

2018-08-05