「BZOJ1355」[Baltic2009] Radio Transmission

2014年12月14日4,2180

Description

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

Input

第一行给出字符串的长度,1 < L ≤ 1,000,000. 第二行给出一个字符串，全由小写字母组成.

Output

输出最短的长度

Sample Input

8
cabcabca

Sample Output

HINT

对于样例,我们可以利用”abc”不断自我连接得到”abcabcabc”,读入的cabcabca,是它的子串

题解

kmp。。。

答案是n-fail[n]，随便画画应该能得到这个结论

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
#define inf 2000000000
#define ll long long 
#define mod 1000000007
using namespace std;
inline int read()
{
    int 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;
}
int n;
char a[1000005];
int fail[1000005];
int main()
{
	n=read();
	scanf("%s",a+1);
	int j=0;
	for(int i=2;i<=n;i++)
	{
		while(a[j+1]!=a[i]&&j)j=fail[j];
		if(a[j+1]==a[i])j++;
		fail[i]=j;
	}
	printf("%d\n",n-fail[n]);
	return 0;
}

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<algorithm>

#include<cmath>

#include<cstring>

#define inf 2000000000

#define ll long long

#define mod 1000000007

using namespace std;

inline int read()

{

int 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;

}

int n;

char a[1000005];

int fail[1000005];

int main()

{

n=read();

scanf("%s",a+1);

int j=0;

for(int i=2;i<=n;i++)

{

while(a[j+1]!=a[i]&&j)j=fail[j];

if(a[j+1]==a[i])j++;

fail[i]=j;

}

printf("%d\n",n-fail[n]);

return 0;

}

« 「CF494B」Obsessive String NOI2014动物园 »

hzwer.com _ Home | http://hzwer.com

「BZOJ1355」[Baltic2009] Radio Transmission

Description

Input

Output

Sample Input

Sample Output

HINT

题解

分类目录

热门文章

Myfriends

近期评论