题意：
给定一个字符串 求重复次数最多的连续重复子串 并输出字典序最小方案
题解：
枚举子串长度L 显然如果重复次数>1 那么答案串肯定包含s[1],s[1+L],s[1+L*2],...中的两个
枚举被答案包含位置 1+L*i
将1+L*i和1+L*(i+1) 向前、向后匹配 记匹配距离和为k 则重复次数为k/L
这样我们就能知道最多重复次数ans是多少
但是这题还要求字典序最小方案
求方案需要再进行一次枚举 方法同上
当重复次数和答案相等时 更新方案
但是我们知道 包含1+L*i 重复次数为k/L 的方案可能有L种 这样总时间就可能达到O(n^2)
因为这L种方案的下标是连续的 并且他们的长度相等
我们可以用线段树维护下标为x到y的rank最小值位置在哪 即可log(n)完成一个询问
总复杂度O(nlog^2(n))
（但是好像常数写好一点不用线段树也能过- - 我就没加跑得比AK加了还快。。）
代码：
#include <cstdio>
#include <cstring>
const int N=;
int n,ans,ansx,ansy,x[N],y[N],sa[N],rank[N],hi[N],ws[N],a[N],lon,min[N][];
char s[N];
void sort(int t){
for (int i=;i<=n;i++) ++ws[x[y[i]]];
for (int i=;i<=t;i++) ws[i]+=ws[i-];
for (int i=n;i;i--) sa[ws[x[y[i]]]--]=y[i];
for (int i=;i<=t;i++) ws[i]=;
}
bool check(int a,int b,int c){ return y[a]==y[b] && y[a+c]==y[b+c]; }
void makesa(){
int p=,tt=;
for (int i=;i<=n;i++) x[i]=a[i],y[i]=i;
sort(tt);
for (int j=;j<=n;j<<=,tt=p,p=){
for (int i=n-j+;i<=n;i++) y[++p]=i;
for (int i=;i<=n;i++)
if (sa[i]>j) y[++p]=sa[i]-j;
sort(tt);
for (int i=;i<=n;i++) y[i]=x[i];
x[sa[]]=p=;
for (int i=;i<=n;i++)
x[sa[i]]=check(sa[i],sa[i-],j) ? p : ++p;
}
}
void makehi(){
for (int i=;i<=n;i++) rank[sa[i]]=i;
for (int i=,k=;i<=n;hi[rank[i++]]=k)
if (rank[i]==) k=;
else for (k=k ? k- : k;a[i+k]==a[sa[rank[i]-]+k];++k);
}
int minn(int x,int y){ return x<y ? x : y; }
void swap(int &x,int &y){ int t=x; x=y,y=t; }
void makemin(){
for (int i=n;i;i--){
min[i][]=hi[i];
for (int j=;i+(<<j)<=n;j++)
min[i][j]=minn(min[i][j-],min[i+(<<(j-))][j-]);
}
}
int find(int t){
int l=,r=,mid;
while (l+<r){
mid=(l+r)/;
if ((<<mid)>t) r=mid;
else l=mid;
}
return l;
}
int getlon(int x,int y){
x=rank[x],y=rank[y];
if (x>y) swap(x,y);
int add=find(y-x);
//while ((1<<add)<=y-x) ++add;
//--add;
return minn(min[x+][add],min[y-(<<add)+][add]);
}
bool checkres(int resx,int resy){
if (!ansx) return ;
int l1=resy-resx+,l2=ansy-ansx+,lon=getlon(resx,ansx);
if (lon>=l1 || lon>=l2) return l1<l2;
return rank[resx]<rank[ansx];
}
void makexy(int x,int y,int z){
for (int i=x;i+z-<=y;i++){
int resx=i,resy=i+z-;
if (checkres(resx,resy)) ansx=resx,ansy=resy;
}
}
void makeans(int bo){
for (int i=;i<lon;i++)
for (int j=+i;j<=lon;j+=i)
if (a[j]==a[j-i]){
int resx=j-i-getlon(n-(j-i)+,n-j+)+,resy=j+getlon(j-i,j)-,lon=resy-resx+,res=lon/i;
if (bo){
if (res==ans) makexy(resx,resy,i*res);
}else if (ans<res) ans=res;
}
}
int main(){
freopen("poj3693.in","r",stdin);
freopen("poj3693.out","w",stdout);
for (int t=;scanf("%s",s),s[]!='#';t++){
printf("Case %d: ",t);
lon=strlen(s);
n=;
for (int i=;i<lon;i++) a[++n]=s[i];
a[++n]='~';
for (int i=lon-;i>=;i--) a[++n]=s[i];
a[n+]=;
ans=;
ansx=ansy=;
makesa();
makehi();
makemin();
makeans();
if (ans==) printf("%c\n",s[sa[]-]);
else{
if (t==)
t=;
makeans();
for (int i=ansx;i<=ansy;i++) printf("%c",s[i-]);
puts("");
}
}
fclose(stdin);
fclose(stdout);
}