BZOJ-1355: [Baltic2009]Radio Transmission

[文章目录]

Description

给你一个字符串,它是由某个字符串不断自我连接形成的。 但是这个字符串是不确定的,现在只想知道它的最短长度是多少.字符串的长度,1 < L ≤ 1,000,000.

自己YY了好久,感觉跟nxt有关,最后发现答案就是长度-整个串的最长前缀后缀的长度。显然可以证明。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int len;
char s[1001000];
int nxt[1001000];
inline void get_nxt()
{
    nxt[0]=-1; int k=-1,i=0;
    while(i<len)
    {
        if(k==-1||s[i]==s[k]) i++,k++,nxt[i]=k;
        else k=nxt[k]; 
    }
}
int main()
{
    scanf("%d%s",&len,s);
    get_nxt();
    printf("%d",len-nxt[len]);
    return 0;
}

发表评论

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