bzoj 2565: 最长双回文串（manacher）

2565: 最长双回文串

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 1605 Solved: 823
[ Submit][ Status][ Discuss]

Description

顺序和逆序读起来完全一样的串叫做回文串。比如 acbca 是回文串，而 abc 不是（ abc 的顺序为 “abc” ，逆序为 “cba” ，不相同）。
输入长度为 n 的串 S ，求 S 的最长双回文子串 T, 即可将 T 分为两部分 X ， Y ，（ |X|,|Y|≥1 ）且 X 和 Y 都是回文串。

Input

一行由小写英文字母组成的字符串S。

Output

一行一个整数，表示最长双回文子串的长度。

Sample Input

baacaabbacabb

Sample Output

HINT

样例说明

从第二个字符开始的字符串aacaabbacabb可分为aacaa与bbacabb两部分，且两者都是回文串。

对于100%的数据，2≤|S|≤10^5

2015.4.25新加数据一组

Source

2012国家集训队Round 1 day2

[ Submit][ Status][ Discuss]

题解：manacher

用manacher求出每个位置的最长回文半径，然后预处理出每个位置向左/向右能覆盖到当前位置的最远的回文中心。利用左右的答案计算最终的答案即可。

注意此题中分成的两部分不能有重叠。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#define N 200003
using namespace std;
int p[N],n,m,l[N],r[N];
char ch[N],s[N];
void manacher()
{
	int mx=0,id;
	for (int i=1;i<=m;i++){
		if (mx>=i) p[i]=min(p[2*id-i],mx-i);
		else p[i]=0;
		for (;ch[i+p[i]+1]==ch[i-p[i]-1];p[i]++);
		if (p[i]+i>mx) mx=p[i]+i,id=i;
	}
}
int main()
{
	freopen("a.in","r",stdin);
	freopen("my.out","w",stdout);
	scanf("%s",s+1);
	ch[0]='S'; n=strlen(s+1);
	for (int i=1;i<=n;i++){
		int pos=i*2;
		ch[pos-1]='#'; ch[pos]=s[i];
	}
	ch[n*2+1]='#';
	m=2*n+1;
	manacher();
	//for (int i=1;i<=m;i++) cout<<ch[i]<<" ";
    //cout<<endl;
	//for (int i=1;i<=m;i++) cout<<p[i]<<" ";
	//cout<<endl; 
	int mx=0;
	for (int i=1;i<=m;i++){
		if (i+p[i]>mx)
		 for (int j=mx+1;j<=i+p[i];j++) l[j]=i;
		mx=max(mx,i+p[i]);
		if (m==mx) break;
	}
	mx=m+1;
	for (int i=m;i>=1;i--){
		if (i-p[i]<mx)
		 for (int j=mx-1;j>=i-p[i];j--) r[j]=i;
		mx=min(mx,i-p[i]);
	    if (mx==1) break;
	}
	//for (int i=1;i<=m;i++) cout<<l[i]<<" ";
	//cout<<endl;
	//for (int i=1;i<=m;i++) cout<<r[i]<<" ";
	//cout<<endl;
	int ans=0;
	for (int i=1;i<=m;i++) 
	 if (ch[i]=='#') {
	 	int t=(i-l[i])*2+1+(r[i]-i)*2+1-1;
	 	ans=max(ans,t/2);
	 }
	printf("%d\n",ans);
}

秒客网