lp4555 国家集训队 最长双回文串

一开始以为是和最长双倍回文串一样的题,不过仔细看一下发现还是简单很多。
总之是麻辣烫(Manacher)的模板题。

Manacher是一\(O(n)\)种处理回文子串的通用方法。
具体来说,对于任意回文串,以它的对称轴为对称轴的所有子串都是回文串;不以它的对称轴为对称轴的所有子串都是对称的。
因此,我们可以分别考虑用着两种情况,使得我们只需要双指针扫一遍即可。
我们记\(f[i]\)表示,以第\(i\)个点为对称轴,最长的回文串半径。
首先我们维护当前对称轴\(mid\)以及当前右端点\(mx\),那么对于第一种情况,只需要拓展右端点即可。
下面我们考虑第二种情况。
首先,对于当前点\(i\),总是有\(i>mid\)。
那么,如果\(i<mx\),那么显然,在对称轴的另一边的点\(j=mid-(i-mid)\),在\(mx\)的范围内,两者必然是拥有共同的子串的。
这样算法就设计完了。

因为是双指针移动,所以复杂度是对的。
然后呢,对于每一个位置\(i\),我们考虑,维护\(l_{i}\)和\(r_{i}\),分别表示,\(i\)所在的回文串中最左的左端点和最右的右端点。
那么,\(ans=Max(r_{i}-l_{i})\)
处理方法的话,维护一个双指针即可。

#include
#include
#include
using namespace std;
#define Max(_A,_B) ((_A)>(_B)?(_A):(_B))
#define Min(_A,_B) ((_A)<(_B)?(_A):(_B))

int n,f[200005],l[200005],r[200005];
char ch[100005],s[200005];
inline void manacher(){
	int mx=0,nw;
	for(int i=2;i<=n;++i){
		if(imx){
			mx=i+f[i];
			nw=i;
		}
	}
}
void init(){
	cin>>(ch+1);
	n=strlen(ch+1);
	s[1]=s[2]='#';
	for(int i=1;i<=n;++i){
		s[(i<<1)+1]=ch[i];
		s[(i<<1)+2]='#';
	}
	n=(n<<1)+2;
	s[n+1]=0;
	manacher();
	int nw=1;
	for(int i=1;i<=n;++i){
		while(nw<=i+f[i]-1){
			l[nw]=i;
			++nw;
		}
	}
	nw=n+1;
	for(int i=n;i>=1;--i){
		while(nw>=i-f[i]+1){
			r[nw]=i;
			--nw;
		}
	}
	int ans=0;
	for(int i=1;i<=n;++i){
		ans=Max(ans,r[i]-l[i]);
	}
	printf("%d\n",ans);
}
int main(){
	init();
	return 0;
}

发表评论

您的电子邮箱地址不会被公开。