首页 > 代码库 > bzoj1355 [Baltic2009]Radio Transmission
bzoj1355 [Baltic2009]Radio Transmission
Description
给你一个字符串，它是由某个字符串不断自我连接形成的。 但是这个字符串是不确定的，现在只想知道它的最短长度是多少.
Input
第一行给出字符串的长度,1 < L ≤ 1,000,000. 第二行给出一个字符串，全由小写字母组成.
Output
输出最短的长度
Sample Input
8
cabcabca
cabcabca
Sample Output
3
HINT
对于样例,我们可以利用"abc"不断自我连接得到"abcabcabc",读入的cabcabca,是它的子串
orz hzwer
直接对这个串进行自匹配，最后输出n-next[n]即是答案
#include<cstdio>#include<iostream>#include<cstring>#include<cstdlib>#include<algorithm>#include<cmath>#include<queue>#include<deque>#include<set>#include<map>#include<ctime>#define LL long long#define inf 0x7ffffff#define pa pair<int,int>#define pi 3.1415926535897932384626433832795028841971using namespace std;inline LL read(){ LL x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f;}inline void write(LL a){ if (a<0){printf("-");a=-a;} if (a>=10)write(a/10); putchar(a%10+‘0‘);}inline void writeln(LL a){write(a);printf("\n");}int l,j;char s[1000010];int next[1000010];int main(){ l=read(); scanf("%s",s+1); for (int i=2;i<=l;i++) { while (j>0 && s[j+1]!=s[i])j=next[j]; if (s[j+1]==s[i])j++; next[i]=j; } printf("%d\n",l-next[l]);}
bzoj1355 [Baltic2009]Radio Transmission
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。