kmp与循环节的关系

对于一个字符串，长度是1~n（需要从1开始，而不是0）,它的最小循环节 T 等于 该字符串的长度 减去 它对应的 next[n]数组，数组的小标是中这个字符串的结尾,

该字符串的循环节长度一定是最小循环节T的整数倍。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;

int n;
char str[N];
int ne[N];

int main()
{
    int T=1;
    while(scanf("%d",&n),n)
    {
        scanf("%s",str+1);
        ne[1]=0;//因为ne[]是全局变量,ne[]默认是0，所以这一行可以不写
        for(int i=2,j=0;i<=n;i++)//得到长度从1~i的每个字符串的ne[]数组
        {
            while(j&&str[i]!=str[j+1]) j=ne[j];
            if(str[i]==str[j+1]) j++;
            ne[i]=j;
        }
        printf("Test case #%d\n",T++);
        for(int i=1;i<=n;i++)
        {
            int j=i-ne[i];//每个字符串的最小循环节，每个字符串的长度是1~i
            if(i%j==0&&i/j>1)
            printf("%d %d\n",i,i/j); 
        }
        puts("");
    }
    return 0;
}