题意：给定一个字符串，求重复次数最多的连续重复子串。
传说中的后缀数组神题，蒟蒻真的调了很久才对啊。感觉对后缀数组和RMQ的模版都不是很熟，导致还是会有很多各种各样的小错误= =
首先，枚举重复子串的循环节为L，因为枚举的是循环节长度，所以是没有单调性的，那么枚举就要用0(n)的时间了。连续一次的情况是可以的，所以这里只考虑重复两次或以上的情况。
记这个连续重复子串为L，我们可以发现，这个字符串一定会覆盖s[0],s[L],s[L*2].....这些点中相邻的两个（因为长度至少为2L嘛）。假设它覆盖的是s[L*i]和s[L*(i+1)]，那么我们就往前和往后计算能匹配多远（往后匹配用到了后缀数组的height数组，往前匹配可以while到s[L*(i-1)]，越过s[L*(i-1)]的情况和前面计算的重复了，可以不算）
记往前匹配和往后匹配的最长长度为k，则重复次数为k/L+1。(如图)
穷举长度L的时间为n，每次计算的时间为n/L。
另外，要在较快的时间内求出以i为开头的后缀和以j为开头的后缀的最长公共前缀要用到RMQ。即快速算出min(height[rank[i]]~height[rank[j]])。用rmq[i][j]表示i~i+(1<<j)-1的min(height)，具体如下。
代码如下：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define Maxn 100100 char s[Maxn];
int a[Maxn],n;
int rank[Maxn],sa[Maxn],Rsort[Maxn],y[Maxn],wr[Maxn];
int height[Maxn],d[Maxn][],ans[Maxn],as[Maxn],al;
int maxx,pos,len; int mymin(int xx,int yy) {return xx<yy?xx:yy;} void get_sa(int m)
{
memcpy(rank,a,sizeof(rank));
for(int i=;i<=m;i++) Rsort[i]=;
for(int i=;i<=n;i++) Rsort[rank[i]]++;
for(int i=;i<=m;i++) Rsort[i]+=Rsort[i-];
for(int i=n;i>=;i--) sa[Rsort[rank[i]]--]=i; int ln=,p=;
while(p<n)
{
int k=;
for(int i=n-ln+;i<=n;i++) y[++k]=i;
for(int i=;i<=n;i++) if(sa[i]>ln) y[++k]=sa[i]-ln;
for(int i=;i<=n;i++) wr[i]=rank[y[i]]; for(int i=;i<=m;i++) Rsort[i]=;
for(int i=;i<=n;i++) Rsort[wr[i]]++;
for(int i=;i<=m;i++) Rsort[i]+=Rsort[i-];
for(int i=n;i>=;i--) sa[Rsort[wr[i]]--]=y[i]; memcpy(wr,rank,sizeof(wr));
p=;rank[sa[]]=;
for(int i=;i<=n;i++)
{
if(wr[sa[i]]!=wr[sa[i-]]||wr[sa[i]+ln]!=wr[sa[i-]+ln]) p++;
rank[sa[i]]=p;
}
m=p,ln*=;
}
sa[]=rank[]=;
} void get_he()
{
int kk=;
for(int i=;i<=n;i++)
{
int j=sa[rank[i]-];
if(kk) kk--;
while(a[i+kk]==a[j+kk]) kk++;
height[rank[i]]=kk;
}
} void rmq_init()
{
for(int i=;i<=n;i++) d[i][]=height[i];
for(int j=;(<<j)<=n;j++)
for(int i=;i+(<<j)-<=n;i++)
d[i][j]=mymin(d[i][j-],d[i+(<<j-)][j-]);
} int rmq(int xx,int yy)
{
int t;
xx=rank[xx],yy=rank[yy];
if(xx>yy) t=xx,xx=yy,yy=t;
xx++;
int kk=;
while((<<(kk+))<=yy-xx+) kk++;
return mymin(d[xx][kk],d[yy-(<<kk)+][kk]);
} void ffind()
{
al=;
maxx=;
for(int i=;i<=n/;i++)
for(int j=;j+i<=n;j+=i)
{
if(a[j]!=a[j+i]) continue;
int kk=rmq(j,j+i),now,r;
now=kk/i+;r=i-kk%i;
//if(now>maxx) maxx=now,ans[al=1]=j,as[al]=i;
//else if(now==maxx) ans[++al]=j,as[al]=i;
int cnt=,p=j;
for(int m=j-;m>j-i&&a[m]==a[m+i]&&m;m--)
{
cnt++;
if(cnt==r) now++,p=m;
else p=rank[p]>rank[m]?m:p;
}
if(now>maxx) maxx=now,pos=p,len=i;
else if(now==maxx&&rank[pos]>rank[p]) pos=p,len=i;
}
} bool cp(int f1,int a1,int f2,int a2)
{
int kk=rmq(f1,f2);
if(kk>=a1-&&kk>=a2-) return a1<=a2?:;
if(kk>=a1-) return ;if(kk>=a2-) return ;
return a[f1+kk]>a[f2+kk];
} int main()
{
int kase=;
while()
{
scanf("%s",s+);
if(s[]=='#') break;
n=strlen(s+);int minn=;
memset(a,,sizeof(a));
for(int i=;i<=n;i++)
{
a[i]=s[i]-'a'+;
minn=mymin(minn,a[i]);
}
get_sa();
get_he();
rmq_init();
ffind();
printf("Case %d: ",++kase);
if(maxx==) printf("%c",minn+'a'-);
else
{
for(int i=pos;i<=pos+len*maxx-;i++) printf("%c",s[i]);
}
printf("\n");
}
return ;
}
poj3693
2015-12-15 17:02:11