●BZOJ 3676 [Apio2014]回文串

时间：2022-10-29 04:43:55

题链:

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

题解：

后缀数组，Manacher，二分

首先有一个结论：一个串的本质不同的回文串的个数不超过 N(串的长度)个。
这个结论可以由 Manacher算法的过程得出。
因为每次在暴力拓展时，
如果当前回文串的右端点大于了记录的MAXR,那么就可能产生了一个之前没有出现过的回文串。
而如果右端点没有超过 MAXR，既不会暴力拓展（即之前已经出现过了），也就更不会产生新的回文串。
（不太懂？再看看这里的东西啦。）
而整个算法中暴力拓展只会拓展N次，所以最多只会产生 N。

既然得到了所有本质不同的回文串，且个数不超过 N个。（只能保证找到了所有的，但可能会有重复的记录）
就下来就只需要在后缀数组中找到该回文串出现了多少次就好了。

代码：

#include<cstdio>

#include<cstring>

#include<iostream>

#define MAXN 305000

#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],stm[MAXN][20];

int start[MAXN],len[MAXN],log2[MAXN],cnt;

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 query(int l,int r){

	static int k;

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

	k=log2[r-l+1];

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

}

void Manacher(int N){

	static char T[2*MAXN];

	static int p[MAXN*2],maxr,pos,lT;

	T[0]='&'; T[1]='#'; lT=2;

	for(int i=0;i<N;i++) T[lT++]=S[i],T[lT++]='#';

	maxr=pos=0;

	for(int i=1;i<lT;i++){

		if(i<maxr) p[i]=min(p[2*pos-i],maxr-i);

		else p[i]=1;

		while(T[i+p[i]]==T[i-p[i]]){

			if(i+p[i]>maxr){

				maxr=i+p[i]; pos=i;

				if(T[i+p[i]-1]!='#')

					cnt++,start[cnt]=(i-p[i]+1)/2-1,len[cnt]=p[i];	//记录回文串

			}

			p[i]++;

		}

	}

	//for(int i=1;i<=cnt;i++) printf("%d %d\n",start[i],len[i]);

}

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

	int pos=p;

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

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

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

		if(query(_p,p)<lim) continue;

		pos=_p;

	}

	return pos;

}

void getans(int N){

	long long ans=0; hei[N]=0;

	for(int i=1,rk,l,r;i<=cnt;i++){

		rk=rak[start[i]];

		l=find(rk,len[i],-1,N);

		r=find(rk,len[i],1,N);

		ans=max(ans,1ll*len[i]*(r-l+1));

	}

	printf("%lld",ans);

}

int main()

{

	log2[1]=0;

	for(register int i=2;i<=300000;i++)

		log2[i]=log2[i>>1]+1;

	scanf("%s",S);

	int N=strlen(S);

	build(N,300);

	Manacher(N);

	getans(N);

	return 0;

}

相关文章