思路:
这个题简直丧心病狂.终于是过了.
注意到重复出现一次的字串必定是字典序最小的字符.我们只考虑重复出现不少于两次的子串.
首先我们枚举重复出现的每一小段的长度\(l\).考虑若干个端点\(0,l,2l,...,i*l,(i+1)*l\),若存在每一小段长度为\(l\)且连续重复出现至少两次的子串,则至少覆盖两个端点.
因此我们枚举相邻的两个端点,分别找出向前最多能匹配多少,向后最多能匹配多少,我们就找到了两个完全相等的段,而且其错开了\(l\)的长度.不妨令其长度为\(d\),则(通过画图)此时的最大重复次数为\(\frac{d}{l}+1\).
如果不要求字典序的话,我们直接这样找到答案就行了.用后缀数组预处理一大堆东西能做到各种询问\(O(1)\)时间复杂度为:
\[\frac{n}{1}+\frac{n}{2}+...+\frac{n}{n}=O(nlogn)\]
因此总的时间复杂度为\(O(nlogn)\).
关键是要求字典序最小.
我们发现每次找到两个完全相等的段时都存在很多合法的答案,也就是若干长度相等,但起点位置不同的子串.我们预处理出起点区间内字典序最小的子串,并利用这个更新答案即可.
不管怎么样,反正时间复杂度\(O(nlogn)\).
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 100010
int len;
char s[N],ss[N];
int v[N],tmpv[N],cnt[N],q[N],sa1[N],sa2[N];
inline bool cmp(int x,int y,int hl,int n){
return v[x]==v[y]&&((x+hl>=n&&y+hl>=n)||(x+hl<n&&y+hl<n&&v[x+hl]==v[y+hl]));
}
inline void calcsa(char*s,int n,int m,int*sa){
register int i,j,k;int hl,id;
for(i=0;i<m;++i)cnt[i]=0;
for(i=0;i<n;++i)++cnt[v[i]=s[i]];
for(i=1;i<m;++i)cnt[i]+=cnt[i-1];
for(i=n-1;i>=0;--i)sa[--cnt[v[i]]]=i;
for(int d=1;;++d){
for(hl=1<<(d-1),id=0,i=n-hl;i<n;++i)q[id++]=i;
for(i=0;i<n;++i)if(sa[i]>=hl)q[id++]=sa[i]-hl;
for(i=0;i<m;++i)cnt[i]=0;
for(i=0;i<n;++i)++cnt[v[q[i]]];
for(i=1;i<m;++i)cnt[i]+=cnt[i-1];
for(i=n-1;i>=0;--i)sa[--cnt[v[q[i]]]]=q[i];
for(m=i=0;i<n;m++,i=j+1){
for(j=i;j<n-1&&cmp(sa[j],sa[j+1],hl,n);++j);
for(k=i;k<=j;++k)tmpv[sa[k]]=m;
}for(i=0;i<n;++i)v[i]=tmpv[i];
if(m==n)break;
}
}
int rk1[N],rk2[N],h1[N],h2[N];
inline void calch(char*s,int n,int*sa,int*rk,int*h){
register int i,j;
for(i=0;i<n;++i)rk[sa[i]]=i;
for(i=0;i<n;++i)if(rk[i]){
j=max(0,h[rk[i-1]]-1);while(i+j<n&&sa[rk[i]-1]+j<n&&s[i+j]==s[sa[rk[i]-1]+j])++j;h[rk[i]]=j;
}
}
int pre[N],rh1[N][21],rh2[N][21];
inline void Initlen(int n){
for(register int i=2;i<=n;++i)pre[i]=pre[i>>1]+1;
}
inline void Initrmq(int*source,int rm[][21],int n){
register int i,j;
for(i=0;i<n;++i)rm[i][0]=source[i];
for(j=1;j<=20;++j)for(i=0;i+(1<<j)-1<n;++i)rm[i][j]=min(rm[i][j-1],rm[i+(1<<(j-1))][j-1]);
}
inline int askmin(int rm[][21],int l,int r){
return min(rm[l][pre[r-l+1]],rm[r-(1<<pre[r-l+1])+1][pre[r-l+1]]);
}
inline int getlcp(int x,int y){
static int rx,ry;rx=rk1[x],ry=rk1[y];if(rx>ry)swap(rx,ry);
return x==y?len-x:askmin(rh1,rx+1,ry);
}
inline int getlcs(int x,int y){
static int rx,ry;rx=rk2[len-1-x],ry=rk2[len-1-y];if(rx>ry)swap(rx,ry);
return x==y?x+1:askmin(rh2,rx+1,ry);
}
int mins[N][21];
inline void Initmins(){
register int i,j;
for(i=0;i<len;++i)mins[i][0]=i;
for(j=1;j<=20;++j)for(i=0;i+(1<<j)-1<len;++i)mins[i][j]=rk1[mins[i][j-1]]<rk1[mins[i+(1<<(j-1))][j-1]]?mins[i][j-1]:mins[i+(1<<(j-1))][j-1];
}
inline int getmins(int l,int r){
int sl=mins[l][pre[r-l+1]],sr=mins[r-(1<<pre[r-l+1])+1][pre[r-l+1]];
return rk1[sl]<rk1[sr]?sl:sr;
}
struct Ans{
int ins,len,t;
Ans(){}
Ans(int _ins,int _len,int _t):ins(_ins),len(_len),t(_t){}
bool operator==(const Ans&B)const{return ins==B.ins&&len==B.len&&t==B.t;}
bool operator<(const Ans&B)const{
if(t!=B.t)return t>B.t;
if(ins==B.ins)return len<B.len;
int rx=rk1[ins],ry=rk1[B.ins],lcp=getlcp(ins,B.ins);
if(len>lcp&&B.len>lcp)return rx<ry;else return len<B.len;
}
}res;
inline void upd(Ans&x,Ans y){if(y<x)x=y;}
int main(){
//freopen("tt.in","r",stdin);
int test=0;
register int i,j;
while(scanf("%s",s)&&s[0]!='#'){
printf("Case %d: ",++test);
len=strlen(s);for(i=0;i<len;++i)ss[i]=s[len-1-i];
calcsa(s,len,256,sa1),calcsa(ss,len,256,sa2);
calch(s,len,sa1,rk1,h1),calch(ss,len,sa2,rk2,h2);
Initlen(len);
Initrmq(h1,rh1,len),Initrmq(h2,rh2,len);
Initmins();
res=Ans(0,0,0);
int lcp,lcs,d;
for(int l=1;l<=len/2;++l){
for(i=0;(i+1)*l<len;++i){
lcp=getlcp(i*l,(i+1)*l);
lcs=getlcs(i*l,(i+1)*l);
d=lcp+lcs-1;
upd(res,Ans(getmins(i*l-lcs+1,(i+1)*l+lcp-(d/l+1)*l),(d/l+1)*l,d/l+1));
}
}
if(res.t==1){
int c=~0U>>1;for(i=0;i<len;++i)c=min(c,(int)s[i]);printf("%c\n",c);
}
else{for(j=0;j<res.len;++j)putchar(s[res.ins+j]);puts("");}
}
return 0;
}