【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 
      
       #include 
       
        #include 
        
         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
         
          >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
          
           >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
           
            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
            
             =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