【Baltic2009】bzoj 1355 Radio Transmission

本文主要是介绍【Baltic2009】bzoj 1355 Radio Transmission，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description 给你一个字符串，它是由某个字符串不断自我连接形成的。 但是这个字符串是不确定的，现在只想知道它的最短长度是多少.
Input 第一行给出字符串的长度,1 < L ≤ 1,000,000. 第二行给出一个字符串，全由小写字母组成. Output
输出最短的长度

对原串进行kmp匹配，那么l-next[l]就是答案。
根据kmp的性质可以知道，s[1..next[l]]==s[next[l]+1..2* next[l]+2]，
s[next[l]+1..2* next[l]+2]==s[2* next[l]+3..3*next[l]+4]
…
以此类推，1..next[l]是原串的子串，又因为next[l]是极大值，所以l-next[l]是极小值。
其实poj2406【见这里】也可以用类似的方法，不过还要判断一下子串长是不是原串的因数。

#include<cstdio>
#include<cstring>
char s[1000010];
int next[1000010];
int main()
{int i,j,k,m,n,p,q,x,y,z,l;scanf("%d%s",&l,s+1);for (i=2,j=0;i<=l;i++){while (j&&s[i]!=s[j+1]) j=next[j];if (s[i]==s[j+1]) j++;next[i]=j;}printf("%d\n",l-next[l]);
}

这篇关于【Baltic2009】bzoj 1355 Radio Transmission的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---