| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 9458 | Accepted: 2915 |
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
Source
重复次数最多的连续重复子串
论文：
先穷举长度 L，然后求长度为 L 的子串最多能连续出现几次。首先连续出现1 次是肯定可以的，所以这里只考虑至少 2 次的情况。假设在原字符串中连续出 现 2 次，记这个子字符串为 S，那么 S 肯定包括了字符 r[0], r[L], r[L*2], r[L*3], ......中的某相邻的两个。所以只须看字符 r[L*i]和 r[L*(i+1)]往前和 往后各能匹配到多远，记这个总长度为 K，那么这里连续出现了 K/L+1 次。最后 看最大值是多少。
穷举长度 L 的时间是 n，每次计算的时间是 n/L。所以整个做法的时间复杂度是 O(n/1+n/2+n/3+......+n/n)=O(nlogn)。
我们不知道它的长度，所以只能枚举长度
对于长度L，他的连续重复子串有的话一定覆盖掉s[1+L*i]中的相邻两个，我们把这样的位置成为“关键点”
所以对于每相邻两个位置(关键点)s[1+L*i]和s[1+L*(i+1)]，求出他们往左和往右能匹配多远l和r(我的r是包括了这个关键点)，然后在这一段内连续重复的次数step=(l+r)/L+1
(因为...自己想想吧，比如对于左端点，移动之后还是相同，还是两个左端点隔了L的距离)
一个重要的问题是字典序最小
对于靠左关键点i，向左能延伸l的话，[i-l,i-l+(l+r)%L]这个区间内开始大小重复次数不变((l+r)%L就是说这一个长度是空余的可以随便左右放)，所以这一段求rnk最小值作为开始，同样对rnk处理ST表
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1e5+,INF=1e9;
int n,m,c[N],t1[N],t2[N];
char s[N]; int mn[N][],Log[N],Pow[];
void iniST(){
Pow[]=;for(int i=;i<;i++) Pow[i]=Pow[i-]<<;
Log[]=-;for(int i=;i<N;i++) Log[i]=Log[i>>]+;
}
void getST(int mn[N][],int a[N]){
for(int i=;i<=n;i++) mn[i][]=a[i];
for(int j=;j<=Log[n];j++)
for(int i=;i+Pow[j]-<=n;i++)
mn[i][j]=min(mn[i][j-],mn[i+Pow[j-]][j-]);
}
int RMQ(int x,int y){
if(x>y) swap(x,y);
int _=Log[y-x+];
return min(mn[x][_],mn[y-Pow[_]+][_]);
}
struct SA{
int sa[N],rnk[N],height[N];
inline bool cmp(int *r,int a,int b,int j){
return a+j<=n&&b+j<=n&&r[a]==r[b]&&r[a+j]==r[b+j];
}
void getSA(char s[]){
m=;
int *r=t1,*k=t2;
for(int i=;i<=m;i++) c[i]=;
for(int i=;i<=n;i++) c[r[i]=s[i]]++;
for(int i=;i<=m;i++) c[i]+=c[i-];
for(int i=n;i>=;i--) sa[c[r[i]]--]=i; for(int j=;j<=n;j<<=){
int p=;
for(int i=n-j+;i<=n;i++) k[++p]=i;
for(int i=;i<=n;i++) if(sa[i]>j) k[++p]=sa[i]-j; for(int i=;i<=m;i++) c[i]=;
for(int i=;i<=n;i++) c[r[k[i]]]++;
for(int i=;i<=m;i++) c[i]+=c[i-];
for(int i=n;i>=;i--) sa[c[r[k[i]]]--]=k[i]; swap(r,k);p=;r[sa[]]=++p;
for(int i=;i<=n;i++) r[sa[i]]=cmp(k,sa[i],sa[i-],j)?p:++p;
if(p>=n) break;m=p;
}
}
void getHeight(char s[]){
for(int i=;i<=n;i++) rnk[sa[i]]=i;
int k=;
for(int i=;i<=n;i++){
if(k) k--;
if(rnk[i]==) continue;
int j=sa[rnk[i]-];
while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k]) k++;
height[rnk[i]]=k;
}
}
int mn[N][];
void ini(char s[]){getSA(s);getHeight(s);getST(mn,height);}
int lcp(int x,int y){
x=rnk[x];y=rnk[y];
if(x>y) swap(x,y);x++;//!!!
int _=Log[y-x+];
return min(mn[x][_],mn[y-Pow[_]+][_]);
}
}a,b; int cas=;
void solve(){
int lexi=INF,mx=,al=,ar=;
for(int L=;L<=n;L++){
for(int i=;i+L<=n;i+=L){
int l=b.lcp(n-i+,n-(i+L)+),r=a.lcp(i,i+L);
int step=(l+r)/L+;
if(step>mx){
mx=step;
int _=RMQ(i-l,i-l+(l+r)%L);
lexi=_;
al=a.sa[_],ar=al+L*step-;
}else if(step==mx){
int _=RMQ(i-l,i-l+(l+r)%L);
if(_<lexi) lexi=_,al=a.sa[_],ar=al+L*step-;
}
}
} printf("Case %d: ",++cas);
reverse(s+,s++n);
for(int i=al;i<=ar;i++) putchar(s[i]);
puts("");
}
int main(){
freopen("in","r",stdin);
iniST();
while(scanf("%s",s+)!=EOF){
if(s[]=='#') break;
n=strlen(s+);
a.ini(s);
//for(int i=1;i<=n;i++) printf("a %d %d %d\n",i,a.rnk[i],a.height[i]);
reverse(s+,s++n);
b.ini(s);
getST(mn,a.rnk);
solve();
}
}
2.26.2017
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1e5+,INF=1e9;
int n,m,c[N],t1[N],t2[N];
char s[N];
inline bool cmp(int *r,int a,int b,int j){
return a+j<=n&&b+j<=n&&r[a]==r[b]&&r[a+j]==r[b+j];
}
int Log[N],Pow[],mn[N][]; void iniST(){
Pow[]=;for(int i=;i<;i++)Pow[i]=Pow[i-]<<;
Log[]=-;for(int i=;i<=;i++)Log[i]=Log[i/]+;
}
void getST(int mn[N][],int a[]){
for(int i=;i<=n;i++) mn[i][]=a[i];
for(int j=;j<=Log[n];j++)
for(int i=;i+Pow[j]-<=n;i++)
mn[i][j]=min(mn[i][j-],mn[i+Pow[j-]][j-]);
} inline int rmq(int x,int y){
int t=Log[y-x+];
return min(mn[x][t],mn[y-Pow[t]+][t]);
} struct SA{
int sa[N],rnk[N],height[N],mn[N][]; void getHeight(){
int k=;
for(int i=;i<=n;i++) rnk[sa[i]]=i;
for(int i=;i<=n;i++){
if(k) k--;
if(rnk[i]==) continue;
int j=sa[rnk[i]-];
while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k]) k++;
height[rnk[i]]=k;
}
}
void getSA(){
int *r=t1,*k=t2;
for(int i=;i<=m;i++) c[i]=;
for(int i=;i<=n;i++) c[r[i]=s[i]]++;
for(int i=;i<=m;i++) c[i]+=c[i-];
for(int i=n;i>=;i--) sa[c[r[i]]--]=i; for(int j=;j<=n;j<<=){
int p=;
for(int i=n-j+;i<=n;i++) k[++p]=i;
for(int i=;i<=n;i++) if(sa[i]>j) k[++p]=sa[i]-j; for(int i=;i<=m;i++) c[i]=;
for(int i=;i<=n;i++) c[r[k[i]]]++;
for(int i=;i<=m;i++) c[i]+=c[i-];
for(int i=n;i>=;i--) sa[c[r[k[i]]]--]=k[i]; swap(r,k);p=;r[sa[]]=++p;
for(int i=;i<=n;i++) r[sa[i]]=cmp(k,sa[i],sa[i-],j)?p:++p;
if(p>=n) break;m=p;
}
} int lcp(int x,int y){
x=rnk[x];y=rnk[y];
if(x>y) swap(x,y);x++;
int t=Log[y-x+];
return min(mn[x][t],mn[y-Pow[t]+][t]);
} void ini(){
m=;
getSA();getHeight();getST(mn,height);
}
void test(){
for(int i=;i<=n;i++) printf("%c ",s[i]);puts("");
for(int i=;i<=n;i++) printf("%d ",rnk[i]);puts("");
for(int i=;i<=n;i++) printf("%d ",sa[i]);puts("");
for(int i=;i<=n;i++) printf("%d ",height[i]);puts("");
puts("");
}
}a,b;
int mx,ans,ansl,ansr;
void solve(int L){//printf("sol %d\n",L);
for(int i=;i+L<=n;i+=L)
if(s[i]==s[i+L]){
int r=a.lcp(i,i+L),l=b.lcp(n-i+,n-i-L+);
int step=(l+r)/L+;//printf("hi %d %d lr %d %d step %d\n",i,L,l,r,step);
if(step>mx) mx=step,ans=INF;//,printf("mx %d\n",mx);
if(step==mx){
int t=rmq(i-l,i-l+(l+r)%L);//printf("t %d\n",t);
if(t<ans){
ans=t;
ansl=a.sa[t],ansr=ansl+mx*L-;
}
}
}
} int main(){
int cas=;
iniST();
while(scanf("%s",s+)!=EOF){
if(s[]=='#') break;
n=strlen(s+);
a.ini();//a.test();
reverse(s+,s++n);
b.ini();//b.test(); getST(mn,a.rnk);
reverse(s+,s++n);
mx=;ans=INF;ansl=ansr=;
for(int i=;i<=n;i++)
if(a.rnk[i]<ans) ans=a.rnk[i],ansl=ansr=i;
for(int L=;L<=n;L++) solve(L); printf("Case %d: ",++cas);
for(int i=ansl;i<=ansr;i++) putchar(s[i]);
puts(""); }
}