[BZOJ1355][Baltic2009]Radio Transmission KMP



可以假设原字符串为AAAA....Aabcd,其中A表示循环节,abcd表示循环节的一部分,那么能够发现n-nxt[n]+1正好是循环节的左半边和右半边拼在一起,也就是整个循环节.因此答案即为n-nxt[n]+1.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 1002333
using namespace std;
char s[N];
int n,nxt[N];
void getnxt()
{
    int j=1,k=0;
    nxt[1]=0;
    while(j<=n)
    {
        if(!k||s[j]==s[k])nxt[++j]=++k;
        else k=nxt[k];
    }
}
int main()
{
    cin>>n;
    scanf("%s",s+1);
    getnxt();
    printf("%d\n",n-nxt[n+1]+1);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注