●BZOJ 2251 [2010Beijing Wc]外星联络

时间：2023-03-09 08:24:19
●BZOJ 2251 [2010Beijing Wc]外星联络

题链：

http://www.lydsy.com/JudgeOnline/problem.php?id=2251

题解：

后缀数组，倍增，RMQ

题意:把重复次数超过 1次的子串按字典序输出它们重复的次数。

构建后缀数组，得到 height[]
按排名从小到大枚举每个后缀 i，
考虑它产生的之前没有出现过的子串是否重复次数大于1次。
用到倍增(不想写二分)求出：
包含 i的最大[l,r]范围使得这个范围内的后缀与 i后缀的 LCP大于当前判断的子串的长度。
然后把合法的子串的重复次数输出即可。

代码： 

#include<cstdio>

#include<cstring>

#include<iostream>

#define MAXN 3500

#define filein(x) freopen(#x".in","r",stdin);

#define fileout(x) freopen(#x".out","w",stdout);

using namespace std;

char S[MAXN];

int	sa[MAXN],rak[MAXN],hei[MAXN],L[MAXN],R[MAXN],stm[MAXN][20],log2[MAXN];

void build(int N,int M){

	static int cc[MAXN],ta[MAXN],tb[MAXN],*x,*y,h,p;

	x=ta; y=tb; h=0;

	for(int i=0;i<M;i++) cc[i]=0;

	for(int i=0;i<N;i++) cc[x[i]=S[i]]++;

	for(int i=1;i<M;i++) cc[i]+=cc[i-1];

	for(int i=N-1;i>=0;i--) sa[--cc[x[i]]]=i;

	for(int k=1;p=0,k<N;k<<=1){

		for(int i=N-k;i<N;i++) y[p++]=i;

		for(int i=0;i<N;i++) if(sa[i]>=k) y[p++]=sa[i]-k;

		for(int i=0;i<M;i++) cc[i]=0;

		for(int i=0;i<N;i++) cc[x[y[i]]]++;

		for(int i=1;i<M;i++) cc[i]+=cc[i-1];

		for(int i=N-1;i>=0;i--) sa[--cc[x[y[i]]]]=y[i];

		swap(x,y); y[N]=-1; x[sa[0]]=0; M=1;

		for(int i=1;i<N;i++)

			x[sa[i]]=y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k]?M-1:M++;

		if(M>=N) break;

	}

	for(int i=0;i<N;i++) rak[sa[i]]=i;

	for(int i=0,j;i<N;i++){

		if(h) h--;

		if(rak[i]){

			j=sa[rak[i]-1];

			while(S[i+h]==S[j+h]) h++;

		}

		stm[rak[i]][0]=hei[rak[i]]=h;

	}

	for(int k=1;k<=log2[N];k++)

		for(int i=(1<<k)-1;i<N;i++)

			stm[i][k]=min(stm[i-(1<<(k-1))][k-1],stm[i][k-1]);

}

int LCP(int l,int r){

	static int k;

	if(l>r) swap(l,r); l++;

	k=log2[r-l+1];

	return min(stm[l+(1<<k)-1][k],stm[r][k]);

}

int find(int p,int lim,int x,int N){

	int pos=p;

	for(int k=log2[N],pp;k>=0;k--){

		pp=pos+x*(1<<k);

		if(pp<0||pp>=N) continue;

		if(LCP(p,pp)<lim) continue;

		pos=pp;

	}

	return pos;

}

int solve(int N){

	for(int i=0,l,r;i<N;i++)

		for(int j=hei[i]+1;sa[i]+j-1<N;j++){

			l=find(i,j,-1,N);

			r=find(i,j,1,N);

			if(r-l+1>1) printf("%d\n",r-l+1);

			if(l==r) break;

		}

}

int main()

{

	int N;

	log2[1]=0; for(int i=2;i<=3000;i++) log2[i]=log2[i>>1]+1;

	scanf("%d %s",&N,S);

	build(N,300);

	solve(N);

	return 0;

}

相关文章