題目

The repetition number of a string is defined as the maximum number R such that the string can be partitioned into R same consecutive substrings. For example, the repetition number of "ababab" is 3 and "ababa" is 1.

Given a string containing lowercase letters, you are to find a substring of it with maximum repetition number.

大意是，給你一個字符串，讓你輸出其中重復次數最多的重復連續(xù)字串，如果次數相同就輸出字典序最小的。

思路

一開始不好想。

首先，枚舉串的長度\(L\)，然后枚舉區(qū)間\([1,L]\)，\([L+1,2*L]\)，會發(fā)現，一個連續(xù)重復子串總會被截頭去尾的被枚舉到。

比如cabababc，在枚舉到長度\(L=2\)的時候,中間的那段baba就會被枚舉到，然而實際上可能是去了頭尾的，注意到LCP求出后后面會多出一段，定義\(R=LCP\)，那么，R%L就是多出來的一段，可以看成是前面少取了L-R%L這一段，然后判斷是不是可以把這一段補上，就完成了第一步:找到一段區(qū)間內的最長重復連續(xù)子串。

然后考慮第二步：要求字典序最小。

我們把這些可能成為答案的串先存起來，然后按照的順序一遍掃描，因為sa天然有序，所以就可以得到最終的答案了。

代碼

#include<cstdio> #include<string.h> #include<algorithm> #include<iostream> #define M 100005 using namespace std; int sa[M],rk[M],t1[M],t2[M],tmp[M],cnt1[M],cnt2[M],H[M]; struct node{int x,id;bool operator < (const node& res)const{if(x!=res.x)return x<res.x;return id<res.id;} }A[M]; void Init(char *s,int n){for(int i=1;i<=n;i++)A[i]=(node){s[i],i};sort(A+1,A+n+1);for(int i=1;i<=n;i++)sa[i]=A[i].id; rk[sa[1]]=1;for(int i=2;i<=n;i++){rk[sa[i]]=rk[sa[i-1]];if(s[sa[i]]!=s[sa[i-1]])rk[sa[i]]++; }for(int l=1;rk[sa[n]]<n;l<<=1){for(int i=0;i<=n;i++)cnt1[i]=cnt2[i]=0;for(int i=1;i<=n;i++)cnt1[t1[i]=rk[i]]++,cnt2[t2[i]=(l+i<=n)?rk[i+l]:0]++;for(int i=1;i<=n;i++)cnt1[i]+=cnt1[i-1],cnt2[i]+=cnt2[i-1];for(int i=n;i>=1;i--)tmp[cnt2[t2[i]]--]=i;for(int i=n;i>=1;i--)sa[cnt1[t1[tmp[i]]]--]=tmp[i];rk[sa[1]]=1;for(int i=2;i<=n;i++){rk[sa[i]]=rk[sa[i-1]];if(t1[sa[i]]!=t1[sa[i-1]]||t2[sa[i]]!=t2[sa[i-1]])rk[sa[i]]++;}}for(int i=1,j=0;i<=n;i++){j-=j>0;while(s[i+j]==s[sa[rk[i]-1]+j])j++;H[rk[i]]=j;} } struct Stable{int mn[M][21],Log[M];void Init(int n){for(int i=1;i<=n;i++){mn[i][0]=H[i];if(i>1)Log[i]=Log[i>>1]+1;}for(int j=1;j<21;j++)for(int i=1;i+(1<<j-1)<=n;i++)mn[i][j]=min(mn[i][j-1],mn[i+(1<<j-1)][j-1]);}int Query(int l,int r){int t=Log[r-l+1];return min(mn[l][t],mn[r-(1<<t)+1][t]);} }st; int LCP(int l,int r){l=rk[l],r=rk[r];if(l>r)swap(l,r);return st.Query(l+1,r); } char S[M]; int n,cas=0,a[M],cnt; int main(){while(scanf("%s",S+1)&&S[1]!='#'){n=strlen(S+1);Init(S,n);st.Init(n);int ans=0;for(int L=1;L<=n;L++){for(int i=1;i<=n;i+=L){int R=LCP(i,i+L),step=R/L+1,k=i-(L-R%L);if(k>=0&&R%L)if(LCP(k,k+L)>=R)step++;if(step>ans){ans=step;cnt=0;a[cnt++]=L;}else if(step==ans)a[cnt++]=L;}}int len=-1,st;for(int i=1;i<=n&&len==-1;i++){for(int j=0;j<cnt;j++){int L=a[j];if(LCP(sa[i],sa[i]+L)>=(ans-1)*L){len=L;st=sa[i];break;}}} printf("Case %d: ",++cas);for(int i=st;i<st+len*ans;i++)printf("%c",S[i]);putchar('\n');for(int i=1;i<=n;i++)S[i]=0;}return 0; }

轉載于:https://www.cnblogs.com/zryabc/p/11202144.html

總結

以上是生活随笔為你收集整理的POJ3693 Maximum repetition substring的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。