首页 > 代码库 > HDU2459[Maximum repetition substring]

HDU2459[Maximum repetition substring]

2024-10-02 13:25:02   218人阅读

Problem Description
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.
 
Input
The input consists of multiple test cases. Each test case contains exactly one line, which
gives a non-empty string consisting of lowercase letters. The length of the string will not be greater than 100,000.
The last test case is followed by a line containing a ‘#‘.
 
Output
For each test case, print a line containing the test case number( beginning with 1) followed by the substring of maximum repetition number. If there are multiple substrings of maximum repetition number, print the lexicographically smallest one.
 
Sample Input
ccabababc
daabbccaa
#
 
Sample Output
Case 1: ababab Case 2: aa
 
<style>pre.cjk { font-family: "Droid Sans Fallback", monospace } p { margin-bottom: 0.25cm; line-height: 120% }</style>

思路{

　　后缀数组处理LCP我还不会。。。。。。。

　　白学后缀数组了。。。。。。。。

　　首先假设一个长度为l的子串重复出现两次，那么它必然会包含s[0]、s[l]、s[l*2]...之中的相邻的两个。不难看出，该重复子串必然会包含s[0..l]或s[l..l*2]或　　　s[l*2..l*3]...。所以，我们可以枚举一个i，对于每个i*l的位置，利用LCP可以求出s[i*l..(i+1)*l]向后延伸的长度 len=LCP(i,i+l)/l+1(可以画一画两段瞧一瞧)。　　i*l..(i+1)*l这一段重复出现的次数。但还有一种情况——前面有比他更优的串！故往前找循环节，但长度为多少呢?最后空出来的为len%l循环节长度为l,故长度　　为l-len%l.

}

 

 1 #include<map>
 2 #include<set>
 3 #include<list>
 4 #include<deque>
 5 #include<cmath>
 6 #include<queue>
 7 #include<stack>
 8 #include<vector>
 9 #include<cstdio>
10 #include<complex>
11 #include<cstring>
12 #include<cstdlib>
13 #include<iostream>
14 #include<algorithm>
15 #define maxx 100010
16 using namespace std;
17 int X[maxx],Y[maxx],sa[maxx],height[maxx],rnk[maxx],tong[maxx];
18 char s[maxx];int num[maxx];
19 bool comp(int *r,int a,int b,int len){return r[a]==r[b]&&r[a+len]==r[b+len];}
20 void build_sa(int n){
21   int *x=X,*y=Y,*t,Max=200;
22   for(int i=0;i<=Max;++i)tong[i]=0;
23   for(int i=0;i<n;++i)tong[x[i]=num[i]]++;
24   for(int i=1;i<=Max;++i)tong[i]+=tong[i-1];
25   for(int i=n-1;i!=-1;i--)sa[--tong[x[i]]]=i;
26   for(int j=1,p=0,i;p<n;Max=p,j<<=1){
27     for(i=n-1,p=0;i>=n-j;--i)y[p++]=i;
28     for(i=0;i<n;++i)if(sa[i]>=j)y[p++]=sa[i]-j;
29     for(i=0;i<=Max;++i)tong[i]=0;
30     for(i=0;i<n;++i)tong[x[y[i]]]++;
31     for(i=1;i<=Max;++i)tong[i]+=tong[i-1];
32     for(i=n-1;i!=-1;i--)sa[--tong[x[y[i]]]]=y[i];
33     for(t=x,x=y,y=t,x[sa[0]]=0,p=1,i=1;i<n;++i)
34       x[sa[i]]=comp(y,sa[i],sa[i-1],j)?p-1:p++;
35   }
36 }int n;
37 void geth(){int i,j,k=0;
38   for(i=1;i<=n;++i)rnk[sa[i]]=i;
39   for(i=0;i<n;height[rnk[i++]]=k)
40     for(k?k--:0,j=sa[rnk[i]-1];num[j+k]==num[i+k];k++);
41 }
42 int dp[maxx][19];
43 void RMQ(){
44   for(int i=1;i<=n;++i)dp[i][0]=height[i];
45   for(int j=1;(1<<j)<=n;++j)
46     for(int i=1;i+(1<<(j-1))<n;++i)
47       dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
48 }
49 LL LCP(int x,int y){
50   x=rnk[x],y=rnk[y];if(x>y)swap(x,y);x++;
51   int t=(int)(log(double(y-x+1))/log(2.000));
52   return min(dp[x][t],dp[y-(1<<t)+1][t]);
53 }
54 int main(){
55   freopen("1.in","r",stdin);
56   freopen("1.out","w",stdout);int T=1;
57   while(scanf("%s",s)&&s[0]!=‘#‘){int ans=0;
58     cout<<"Case "<<T<<": ";T++;
59     memset(X,0,sizeof(X));
60     memset(Y,0,sizeof(Y));
61     memset(sa,0,sizeof(sa));
62     memset(height,0,sizeof(height));
63     memset(rnk,0,sizeof(rnk));n=strlen(s);
64     for(int i=0;i<n;++i)num[i]=s[i]-90;num[n]=0;
65     build_sa(n+1),geth(),RMQ();int P,pos,nu,cnt,len,t;
66     for(int i=1;i<=(n>>1);++i)
67       for(int j=0;j+i<n;j+=i){
68     if(num[j]!=num[j+i])continue;
69     int L=LCP(j,j+i);
70     nu=L/i+1;pos=j;
71     t=i-L%i;cnt=0;
72     for(int k=j-1;k>=0&&k+i>j&&num[k]==num[k+i];k--){
73       cnt++;
74       if(cnt==t)nu++,pos=k;
75       else if(rnk[k]<rnk[pos])pos=k;
76     }
77     if(ans<nu)ans=nu,P=pos,len=i;
78     else if(rnk[P]>rnk[pos]&&ans==nu)P=pos,len=i;
79       }
80     for(int i=P;i<P+ans*len;++i)cout<<s[i];
81     cout<<‘\n‘;
82   }
83   return 0;
84 }

 

 

 

 

HDU2459[Maximum repetition substring]


联系
我们