Repeats

hihoCoder 1419 后綴數(shù)組四·重復旋律4(重復次數(shù)最多的連續(xù)子串)

#include<bits/stdc++.h> using namespace std;// sa[i]: 排名是i位的是第幾個后綴 // rk[i]: 第i個后綴的排名是多少 // height[i]: sa[i]與sa[i-1] const int N=50010; char s[N]; int rk[N],sa[N],cnt[N],height[N]; int x[N],y[N]; int n,m; void rsort()// x[i] 第一關(guān)鍵字 y[i] 第二關(guān)鍵字 基數(shù)排序 {for(int i=1;i<=m;i++) cnt[i]=0;for(int i=1;i<=n;i++) cnt[x[i]]++;for(int i=1;i<=m;i++) cnt[i]+=cnt[i-1];for(int i=n;i;i--) sa[cnt[x[y[i]]]--]=y[i]; } void SA() {n=strlen(s+1);m=300;for(int i=1;i<=n;i++) x[i]=s[i],y[i]=i;rsort();for(int k=1;k<=n;k<<=1){int p=0;for(int i=n-k+1;i<=n;i++) y[++p]=i;// 第二關(guān)鍵字為空字符排在最前面for(int i=1;i<=n;i++) if(sa[i]>k) y[++p]=sa[i]-k;rsort();swap(x,y);x[sa[1]]=1,p=1;for(int i=2;i<=n;i++)x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k]?p:++p);if(p==n) break;m=p;}for(int i=1;i<=n;i++) rk[sa[i]]=i;// 求heightfor(int i=1,j=0;i<=n;i++){if(j) --j;while(s[i+j]==s[sa[rk[i]-1]+j]) j++;height[rk[i]]=j;} } int st[N][22],lg[N]; void init() {for(int i=1;i<=n;i++) st[i][0]=height[i];for(int k=1;k<=lg[n];k++)for(int i=1;i+(1<<k)-1<=n;i++)st[i][k]=min(st[i][k-1],st[i+(1<<k-1)][k-1]); } int lcp(int a,int b) {int l=min(rk[a],rk[b])+1;int r=max(rk[a],rk[b]);int k=lg[r-l+1];return min(st[l][k],st[r-(1<<k)+1][k]); } int solve() {int ans=1;for(int l=1;l<=n;l++)for(int i=1;i+l<=n;i+=l){int r=lcp(i,i+l);ans=max(ans,r/l+1);if(i>=l-r%l) ans=max(ans,lcp(i-l+r%l,i+r%l)/l+1);}return ans; } int main() {for(int i=2;i<=50000;i++) lg[i]=lg[i>>1]+1;int Tc;scanf("%d",&Tc);while(Tc--){scanf("%d",&n);for(int i=1;i<=n;i++)scanf(" %c",&s[i]);s[n+1]='\0';SA();init();printf("%d\n",solve());}return 0; }

總結(jié)

以上是生活随笔為你收集整理的SPOJ687 Repeats（重复次数最多的连续子串）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。