首页 > 代码库 > bzoj2320: 最多重复子串
bzoj2320: 最多重复子串
2320: 最多重复子串
Time Limit: 40 Sec Memory Limit: 128 MBSubmit: 246 Solved: 66
[Submit][Status][Discuss]
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
ccabababc
daabbccaa
Sample Output
ababab
aa
HINT
100%:T≤10,S的长度不超过100000
题解
……我就来贴个代码吧……orz下claris……
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 typedef unsigned long long ll; 5 const int N=100010,base=127; 6 int ans,k,st,ed,n,m,time,i,l;char s[N];ll f[N],pow[N]; 7 using namespace std; 8 ll hash(int l,int r){return f[r]-f[l-1]*pow[r-l+1];} 9 int lcs(int x,int y) 10 { 11 int l=0,r=min(x,y); 12 while(l<r){ 13 int mid=(l+r)/2; 14 if(hash(x-mid,x)==hash(y-mid,y))l=mid+1;else r=mid; 15 } 16 return l; 17 } 18 int lcp(int x,int y) 19 { 20 int l=0,r=min(n-x+1,n-y+1); 21 while(l<r){ 22 int mid=(l+r)/2; 23 int a=hash(x,x+mid); 24 int b=hash(y,y+mid); 25 if(hash(x,x+mid)==hash(y,y+mid))l=mid+1;else r=mid; 26 } 27 return l; 28 } 29 void up(int x,int y) 30 { 31 if(k>ans){ans=k;st=x;ed=y;return;} 32 int l0=ed-st+1,l1=y-x+1,t=lcp(x,st); 33 if(t==min(l0,l1)){ 34 if(t==l0)return; 35 st=x;ed=y;return; 36 } 37 if(s[st+t]>s[x+t]){st=x;ed=y;} 38 } 39 int main() 40 { 41 scanf("%d",&time); 42 for(i=1,pow[0]=1;i<=N;i++)pow[i]=pow[i-1]*base; 43 while(time--) 44 { 45 scanf("%s",s+1);n=strlen(s+1); 46 for(ans=st=ed=i=1;i<=n;i++) 47 if(s[i]<s[st])st=ed=i; 48 for(f[0]=0,i=1;i<=n;i++)f[i]=f[i-1]*base+s[i]; 49 for(int i=1;i<=n/2;i++) 50 for(int j=1;j<=n;j+=i){ 51 int x=j+i;if(x>n)break; 52 if(s[j]!=s[x])continue; 53 int a=lcp(j,x),b=lcs(j,x); 54 k=(a+b-1)/i+1; 55 l=k*i; 56 if(k>=ans)for(int y=j-b+1;y<=i+j+a-l;y++)up(y,y+l-1); 57 } 58 for(int i=st;i<=ed;i++)putchar(s[i]);puts(""); 59 } 60 return 0; 61 }
bzoj2320: 最多重复子串
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。