首页 > 代码库 > 【poj3693-重复次数最多的连续重复子串】后缀数组
【poj3693-重复次数最多的连续重复子串】后缀数组
题意：给定一个串，长度<=10^5，求它重复次数最多的连续重复子串（输出字典序最小的那个）。
例如ccabcabc，答案就是abcabc
一开始没想清楚，结果调了好久。
对于当前的L，i，i+1，x=s[i*L]，y=s[(i+1)*L]，找前找后，知道了最早能匹配到t0，最晚能匹配到t1，因为不知道当前的起始点是真正循环节的第几个点，所以我们要往前找L个点看看它们是不是真正的起始点。
细节就看代码吧：
#include<cstdio>#include<cstdlib>#include<cstring>#include<iostream>using namespace std;const int N=2*100100;int cl,rk[N],sa[N],Rs[N],y[N],wr[N],h[N],r[N][30];char c[N];int minn(int x,int y){return x<y ? x:y;}void get_sa(int m){ for(int i=1;i<=cl;i++) rk[i]=c[i]-‘a‘+1; for(int i=1;i<=m;i++) Rs[i]=0; for(int i=1;i<=cl;i++) Rs[rk[i]]++; for(int i=1;i<=m;i++) Rs[i]+=Rs[i-1]; for(int i=cl;i>=1;i--) sa[Rs[rk[i]]--]=i; int ln=1,p=0; while(p<cl) { int k=0; for(int i=cl-ln+1;i<=cl;i++) y[++k]=i; for(int i=1;i<=cl;i++) if(sa[i]>ln) y[++k]=sa[i]-ln; for(int i=1;i<=cl;i++) wr[i]=rk[y[i]]; for(int i=1;i<=m;i++) Rs[i]=0; for(int i=1;i<=cl;i++) Rs[wr[i]]++; for(int i=1;i<=m;i++) Rs[i]+=Rs[i-1]; for(int i=cl;i>=1;i--) sa[Rs[wr[i]]--]=y[i]; for(int i=1;i<=cl;i++) wr[i]=rk[i]; for(int i=cl+1;i<=cl+ln;i++) wr[i]=0; p=1;rk[sa[1]]=1; for(int i=2;i<=cl;i++) { if(wr[sa[i]]!=wr[sa[i-1]] || wr[sa[i]+ln]!=wr[sa[i-1]+ln]) p++; rk[sa[i]]=p; } ln*=2,m=p; } sa[0]=0,rk[0]=0;}void get_h(){ int k=0,j; for(int i=1;i<=cl;i++) if(rk[i]!=1) { j=sa[rk[i]-1]; if(k) k--; while(c[j+k]==c[i+k] && j+k<=cl && i+k<=cl) k++; h[rk[i]]=k; } h[1]=0;}void get_rmq(){ for(int i=1;i<=cl;i++) r[i][0]=h[i]; for(int j=1;(1<<j)<=cl;j++) for(int i=1;i+(1<<j)-1<=cl;i++) { r[i][j]=minn(r[i][j-1],r[i+(1<<(j-1))][j-1]); }}int query_rmq(int i,int j){ if(i>j) swap(i,j); i++; int k=0; while(i+(1<<(k+1)) <= j) k++; return minn(r[i][k],r[j-(1<<k)+1][k]);}int main(){ int x,y,z,t0,t1,now,ans,al,ar,T=0; while(1) { scanf("%s",c+1); cl=strlen(c+1); if(cl==1 && c[1]==‘#‘) return 0; printf("Case %d: ",++T); get_sa(30); get_h(); get_rmq(); ans=0;al=ar=0; for(int L=1;L*2<=cl;L++) { for(int i=0;L*(i+1)+1<=cl;i++) { x=L*i+1,y=L*(i+1)+1; if(c[x]!=c[y]) continue; z=query_rmq(rk[x],rk[y]); t1=y+z-1; t0=0; for(int j=0;j<=L-1;j++)//往前匹配 { if(x-j<1 || c[x-j]!=c[y-j]) break; t0=x-j; now=((t1-t0+1)/L); if(now>ans || (now==ans && rk[t0]<rk[al])) ans=now,al=t0,ar=t0+now*L-1; } } } if(ans==0) printf("%c\n",c[sa[1]]); else { for(int i=al;i<=ar;i++) printf("%c",c[i]);printf("\n"); } } return 0;}
【poj3693-重复次数最多的连续重复子串】后缀数组
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。