Cyclic Nacklace（最小循环节问题）

题目链接hud3746

kmp求最小循环节

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

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

（2）如果不能，说明还需要再添加几个字母才能补全。需要补的个数是循环个数 res = cnt - slen%cnt;

int k = Next[slen];
int cnt = slen - Next[slen] ;

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define N 2000000
using namespace std;
int Next[N];
char str[N];
void getnext(char *p,int plen)
{
    Next[0]=0;Next[1] = 0;for(int i=1;i<plen;i++){
    int j =Next[i];while(j&&p[i]!=p[j]) j=Next[j];Next[i+1] = (p[i]==p[j])?j+1:0;}
}int main()
{
    int t;cin>>t;while(t--){
    scanf("%s",&str);memset(Next,0,sizeof(Next));int slen = strlen(str);getnext(str,slen);int k = Next[slen];int cnt = slen - Next[slen];if(k==0)cout<<slen<<endl;else if(slen%cnt==0)cout<<0<<endl;//cout<<slen<<" "<<cnt<<endl;else if(slen%cnt!=0){
    int res =0;res = cnt - slen%cnt;cout<<res<<endl;}}}