首页 > 代码库 > URAL 1517 Freedom of Choice(后缀数组,最长公共字串)
URAL 1517 Freedom of Choice(后缀数组,最长公共字串)
题目
输出最长公共字串
#define maxn 200010int wa[maxn],wb[maxn],wv[maxn],ws[maxn];int cmp(int *r,int a,int b,int l){return r[a]==r[b]&&r[a+l]==r[b+l];}//yuan lai zhi qian ba zhe li de l cuo dang cheng 1 le ...void da(int *r,int *sa,int n,int m){ int i,j,p,*x=wa,*y=wb,*t; for(i=0;i<m;i++)ws[i]=0; for(i=0;i<n;i++)ws[x[i]=r[i]]++; for(i=1;i<m;i++)ws[i]+=ws[i-1]; for(i=n-1;i>=0;i--)sa[--ws[x[i]]]=i; for(j=1,p=1;p<n;j*=2,m=p) { for(p=0,i=n-j;i<n;i++)y[p++]=i; for(i=0;i<n;i++)if(sa[i]>=j) y[p++]=sa[i]-j; for(i=0;i<n;i++)wv[i]=x[y[i]]; for(i=0;i<m;i++)ws[i]=0; for(i=0;i<n;i++)ws[wv[i]]++; for(i=1;i<m;i++)ws[i]+=ws[i-1]; for(i=n-1;i>=0;i--)sa[--ws[wv[i]]]=y[i]; for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++) x[sa[i]]=cmp(y,sa[i-1],sa[i],j)? (p-1):p++; }}int rankk[maxn],height[maxn];void calheight(int *r,int *sa,int n){ int i,j,k=0; for(i=1;i<=n;i++)rankk[sa[i]]=i; for(i=0;i<n;height[rankk[i++]]=k) for(k? k--:0,j=sa[rankk[i]-1];r[i+k]==r[j+k];k++);}int RMQ[maxn];int mm[maxn];int best[20][maxn];void initRMQ(int n){ int i,j,a,b; for(mm[0]=-1,i=1;i<=n;i++) mm[i]=((i&(i-1))==0) ? mm[i-1]+1:mm[i-1]; for(i=1;i<=n;i++)best[0][i]=i; for(i=1;i<=mm[n];i++) for(j=1;j<=n+1-(1<<i);j++) { a=best[i-1][j]; b=best[i-1][j+(1<<(i-1))]; if(RMQ[a]<RMQ[b])best[i][j]=a; else best[i][j]=b; }}int askRMQ(int a,int b){ int t; t=mm[b-a+1];b-=(1<<t)-1; a=best[t][a];b=best[t][b]; return RMQ[a]<RMQ[b]? a:b;}int lcp(int a,int b){ int t; a=rankk[a]; b=rankk[b]; if(a>b) {t=a;a=b;b=t;} return (height[askRMQ(a+1,b)]);} char s[maxn]; int r[maxn],sa[maxn];int main(){ int t; while(scanf("%d",&t)!=EOF) { scanf("%s",s); int len1=strlen(s); s[len1]=‘0‘;//yin wei bu ce ng chu xian ,suo yi bu yong dan xin ying xiang jie guo scanf("%s",s+len1+1); int len2=strlen(s); for(int i=0;i<len2;i++)r[i]=s[i];//r[i]biao shi pai de shi di ji r[len2]=0;//ji shu pai xu shi de xu yao ,zui hou yi ge jia she wei zui xiao da(r,sa,len2+1,130); calheight(r,sa,len2); int ans=0,be=-1; //bian li height shu zu, cong di 2 ge kai shi (xia biao shi cong 1 kai shi de ) for(int i=2;i<=len2;i++) { if(height[i]>ans) { if((len1<sa[i]&&len1>sa[i-1])||(len1>sa[i]&&len1<sa[i-1])) { ans=height[i];be=sa[i]; } } } if(be!=-1) for(int i=be;i<be+ans;i++)printf("%c",s[i]); printf("\n"); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。