先把结论摆出来:对于长为j的字符串str[1..j],next[j]=k,则令d=j-k;如果j%d==0，则这个字符串是一个
周期串，前d个字符是其最小的循环结，共包含j/d个循环节。
现在来解决两个问题：
1)前d个字符是其循环结
下标 1 2 3 4 5 6 7 8
字符串 a b a b a b a b
next值 0 0 1 2 3 4 5 6
next[j]=k表示str[1…k]与str[j-k+1..j]是完全相等的;d=j-k所以str[1]=str[d+1]=str[j-k+1],
同样str[2]=str[d+2]=str[j-k+2]……..str[d]=str[j-k+d].这样就证明了第1个循环节和第2个循环节是完全相等的。
于此类似由next数组的性质()我们也可以证明第3个循环节和第2个循环节也是相等的………。最后我们可以证明所有的循环节都和第一个循环节相等，所以第一个循环节是字符串的循环节。
我们可以用上面的字符串做一个演示：next[8]=6表示str[1…6]与str[3..5]完全相等；
d=8-6=2,共有8/2=4个循环节,第一个循环结为ab。然后由str[3]=str[1],str[4]=str[2]可知第二个循环节应为ab(实际上也是)然后由str[5]=str[3],str[6]=str[4]可知第三个循环节也为ab,然后由str[7]=str[5],str[8]=str[6]可知第四个循环结为ab。
所以我们可以看到第一个循环节确实是整个字符串的循环节。
2)前d个字符是其最小的循环结
这一点比较容易证明，next[j]=k表示的是以第j个字符作为结尾的字符后缀与第一个字符开头的字符前缀最多有k个字符是想同的，即str[1—d]至多与str[j-k+1，j-k+d]相等，如果进一步减少d值next数组的性质就不能保证str[d]==str[j-k+d]成立，即前d个字符就不能作为一个循环节了。
代码如下
#include<iostream>#include<cstring>#include<cstdio>using namespace std;char str[1110000];int next[1100000];void Getnext(){int j=0;int len=strlen(str+1);next[1]=0;for(int i=2;i<=len;i++){while(j>0&&str[j+1]!=str[i])j=next[j];if(str[j+1]==str[i])j++;next[i]=j;}}int main(){while(scanf("%s",str+1)){if(str[1]=='.')break;Getnext();int len=strlen(str+1);if(len%(len-next[len])==0){printf("%d\n",len/(len-next[len]));continue;}printf("1\n");} return 0;}
，会让你的心态更平和更坦然，
