POJ3693 Maximum repetition substring 后缀数组

思路:

这个题简直丧心病狂.终于是过了.

注意到重复出现一次的字串必定是字典序最小的字符.我们只考虑重复出现不少于两次的子串.

首先我们枚举重复出现的每一小段的长度\(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;
}