POJ1961Period(kmp+循环节)

题目大意：输出字符串所有前缀的循环节个数，下标从1开始，i 和1-i循环节的个数

题解：网上摘得

KMP最小循环节、循环周期：

定理：假设S的长度为len，则S存在最小循环节，循环节的长度L为len-next[len]，子串为S[0…len-next[len]-1]。

（1）如果len可以被len - next[len]整除，则表明字符串S可以完全由循环节循环组成，循环周期T=len/L。

（2）如果不能，说明还需要再添加几个字母才能补全。需要补的个数是循环个数L-len%L=L-(len-L)%L=L-next[len]%L，L=len-next[len]。

代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define N 1000009

using namespace std;

int n,len;

char s[N];

int nxt[N];

void getnext()

{

    memset(nxt,,sizeof(nxt));

    for(int i=,j=;i<=len;i++)

    {

        while(s[i]!=s[j+]&&j) j=nxt[j];

        if(s[i]==s[j+]) nxt[i]=++j;

    }

}

int main()

{

    while()

    {

        scanf("%d",&len);

        if(!len) break;

        scanf("%s",s+);

        getnext();

        cout<<"Test case #"<<++n<<endl;

        for(int i=;i<=len;i++)

        {

              int k=i-nxt[i];

              if(i!=k&&i%k==)

              printf("%d %d\n",i,i/k);

        }

        printf("\n");

    }

    return ;

}

巴特西

POJ1961Period(kmp+循环节)

最新文章

热门文章