首页 > 代码库 > 【BZOJ2342】【Shoi2011】双倍回文 Manacher+枚举+最优性剪枝

【BZOJ2342】【Shoi2011】双倍回文 Manacher+枚举+最优性剪枝

题解:Manacher处理出回文半径,然后知道一个回文串后就可以知道两边的回文中心,然后O(1)check是否合法,即判断两边中心的回文半径。


这里需要枚举每一个位置的回文半径,因为比如这个 

18
abbbaabbbaccddddcc

ccddddcc就不是双倍回文,但是它中间有个dddd是双倍回文,如果每个回文只check最长的是不是双倍回文,就会WA在这里。

Manacher算法:http://blog.csdn.net/vmurder/article/details/42119417

所以需要枚举一下。。

贴代码:(我把代码略缩了点行,WA了留言我)

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 501000
using namespace std;
char ts[N],s[N<<1];
int n,len,p[N<<1];
void manacher()
{
	int i,j,k,mx=0,id;
	scanf("%s",ts+1);
	/*n=strlen(ts+1),*/len=n*2+1;
	s[0]='*',s[1]='~';
	for(i=1;i<=n;i++)s[i*2]=ts[i],s[i*2+1]='~';
	for(i=1;i<=len;i++)
	{
		if(mx>i)p[i]=min(p[id*2-i],mx-i);
		else p[i]=1;
		while(s[i-p[i]]==s[i+p[i]])p[i]++;
		if(mx<i+p[i])mx=i+p[i],id=i;
	}
	return ;
}
int main()
{
	scanf("%d",&n);
	manacher();
	int ans=0;
	for(int i=1;i<=len;i+=2)
	{
		for(int j=((p[i]-1)>>1)-(j&1);j>0&&j*2>ans;j-=2)
		if(p[i-j]-1>=j&&p[i+j]-1>=j)ans=max(ans,2*j);
	}
	printf("%d\n",ans);
	return 0;
}


复制去Google翻译翻译结果

【BZOJ2342】【Shoi2011】双倍回文 Manacher+枚举+最优性剪枝