首页 > 其他 > 详细

【BZOJ2320】最多重复子串 调和级数+hash

时间:2017-09-24 10:34:00      阅读:294      评论:0      收藏:0      [点我收藏+]

【BZOJ2320】最多重复子串

Description

一个字符串P的重复数定义为最大的整数R,使得P可以分为R段连续且相同的子串。比方说,“ababab”的重复数为3,“ababa”的重复数为1。

Your Task

对于给定的串S,找出S的一个子串K使得K的重复数最大。

Input

第一行T表示数据组数

对于每组数据,一行中一个仅包含小写字母的字符串S

Output

对于每组数据,在一行中输出K,如果有多个解,输出字典序最小的那一个

Sample Input

2
ccabababc
daabbccaa

Sample Output

ababab
aa

HINT

100%:T≤10,S的长度不超过100000

题解:居然能第二次遇到这种套路,真是不容易(第一次在股市的预测)。

如果重复数为1,则答案就是最小的字符,下面只考虑重复数不是1的情况。

回忆next数组的性质,一个串的最小循环节为n-next[n](如果有的话),而我们要枚举什么呢?我们枚举的就是0~n-next[n]以及next[n]~n的部分。

具体地,我们枚举循环节的长度为len,然后每隔len的长度设一个关键点,这样就保证了每个循环节都只包含一个关键点。然后我们对于每个关键点i,求出它和下一个关键点的最长公共前缀A和最长公共后缀B,用$\lfloor{A+B-1\over len}\rfloor+1$更新答案。

如何求字典序最小呢?因为极长重复串的个数是O(n)的(Claris说的。。。),所以暴力判断即可。

时间复杂度取决于如何求LCP和LCS,如果用hash+二分的话是$O(nlog^2n)$的。

 

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
typedef unsigned long long ull;
const int maxn=100010;
int n,ans,ap,bp;
ull hs[maxn],bs[maxn];
char str[maxn];
inline ull hash(int a,int b)	{return hs[b]-((!a)?0:hs[a-1]*bs[b-a+1]);}
inline int lcs(int a,int b)
{
	int l=0,r=min(a,b)+2,mid;
	while(l<r)
	{
		mid=(l+r)>>1;
		if(hash(a-mid+1,a)==hash(b-mid+1,b))	l=mid+1;
		else	r=mid;
	}
	return l-1;
}
inline int lcp(int a,int b)
{
	int l=0,r=n-max(a,b)+1,mid;
	while(l<r)
	{
		mid=(l+r)>>1;
		if(hash(a,a+mid-1)==hash(b,b+mid-1))	l=mid+1;
		else	r=mid;
	}
	return l-1;
}
void updata(int a,int b)
{
	if(ap==-1)	ap=a,bp=b;
	else
	{
		int l1=b-a+1,l0=bp-ap+1,k=min(lcp(a,ap),min(l1,l0));
		if((k<=l1?str[a+k]:0)<(k<=l0?str[ap+k]:0))	ap=a,bp=b;
	}
}
inline void calc(int x)
{
	for(int i=0,a,b,c;i+x<n;i+=x)	if(str[i]==str[i+x])
	{
		a=lcs(i,i+x),b=lcp(i,i+x),c=(a+b-1)/x+1;
		if(c>ans)	ans=c,ap=bp=-1;
		if(ans!=1&&c==ans)	for(int j=i-a+1;j+c*x-1<=i+x+b-1;j++)	updata(j,j+c*x-1);
	}
}
void work()
{
	scanf("%s",str),n=strlen(str),ans=1,ap=bp=-1;
	int i;
	for(bs[0]=1,i=1;i<=n;i++)	bs[i]=bs[i-1]*131;
	for(i=0;i<n;i++)	hs[i]=((!i)?0:hs[i-1])*131+str[i],ap=(ap==-1||str[i]<str[ap])?i:ap,bp=ap;
	for(i=1;i<=n&&n/i>=ans;i++)	calc(i);
	for(i=ap;i<=bp;i++)	printf("%c",str[i]);
	printf("\n");
}
int main()
{
	int T;	scanf("%d",&T);
	while(T--)	work();
	return 0;
}//1 ababacac

 

【BZOJ2320】最多重复子串 调和级数+hash

原文:http://www.cnblogs.com/CQzhangyu/p/7586456.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!