1355: [Baltic2009]Radio Transmission
1355: [Baltic2009]Radio Transmission
attack
发布于 2018-04-12 11:17:56
发布于 2018-04-12 11:17:56
Description
给你一个字符串，它是由某个字符串不断自我连接形成的。 但是这个字符串是不确定的，现在只想知道它的最短长度是多少.
Input
第一行给出字符串的长度,1 < L ≤ 1,000,000. 第二行给出一个字符串，全由小写字母组成.
Output
输出最短的长度
Sample Input
8 cabcabca
Sample Output
3
HINT
对于样例,我们可以利用"abc"不断自我连接得到"abcabcabc",读入的cabcabca,是它的子串
Source
KMP算法的裸题
答案=L-P[L];
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<cstring>
6 #include<algorithm>
7 using namespace std;
8 const int MAXN=1000010;
9 void read(int &n)
10 {
11 char c='+';int x=0;bool flag=0;
12 while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
13 while(c>='0'&&c<='9')x=x*10+c-48,c=getchar();
14 n=flag==1?-x:x;
15 }
16 char a[MAXN];
17 int p[MAXN];
18 int l=0;
19 void getp()
20 {
21 int j=0;
22 for(int i=1;i<l;i++)
23 {
24 while(a[i]!=a[j]&&j>0) j=p[j-1];
25 if(a[i]==a[j])j++;
26 p[i]=j;
27 }
28 printf("%d",l-p[l-1]);
29 }
30 int main()
31 {
32 int meiyong;read(meiyong);
33 scanf("%s",a);
34 l=strlen(a);
35 getp();
36 return 0;
37 }本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-08-12 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录