kmpTag ArchiveSubscribe

题目地址

题意就是让求整个字符串最小循环节的长度。字符串长度小于100。
可以直接上kmp。就算长度一千万也可以搞。
当i-nxt[i]能整除i的时候，i-nxt[i]就是最小循环节的长度

#include<bits/stdc++.h>
using namespace std;
char a[111];
int nxt[111];
int n;
void kmp()
{
    nxt[1]=0;
    for(int i=2,j=0;i<=n;i++)
    {
        while(j>0 && a[i]!=a[j+1]) j=nxt[j];
        if(a[i]==a[j+1]) j++;
        nxt[i]=j;
    }
}
int main()
{
    scanf("%s",a+1);
    n=strlen(a+1);
    kmp();
    if(n%(n-nxt[n])==0) printf("%d",n-nxt[n]);
    else printf("%d",n);
}