bzoj 2565: 最长双回文串 manacher算法

2565: 最长双回文串

Time Limit: 20 Sec  Memory Limit: 256 MB

题目连接

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

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

12

HINT

题意

 

题解：

马拉车算法先跑一法回文串长度，然后再dp一下，对于每个字符的位置，记录下这个点为左端点的回文串长度，这个点为右端点的回文串长度

对于如何存dp的值，我是暴力的，再加了个小小的剪枝

然后跑一法就好了

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+7;
char s[maxn];
char str[maxn];
int p[maxn];
int dp1[maxn];
int dp2[maxn];
int l;
void manacher(char s[],int l)
{int i,j,k,ans=0;for(i=1;i<=l;++i)str[i<<1]=s[i],str[(i<<1)+1]='#';str[1]='#';str[l*2+1]='#';str[0]='&';str[l*2+2]='$';l=l*2+1;j=0;for(i=1;i<=l;){while(str[i-j-1]==str[i+j+1])++j;p[i]=j;if(j>ans)ans=j;for(k=1;k<=j&&p[i]-k!=p[i-k];++k)p[i+k]=min(p[i-k],p[i]-k);i+=k;j=max(j-k,0);}
}
int main()
{//test;scanf("%s",s+1);l=strlen(s+1);manacher(s,l);l=l*2+1;for(int i=1;i<=l;i++){for(int j=p[i];j>=1;j--){if(dp1[i+j]>=j)break;dp1[i+j]=j;}for(int j=p[i];j>=1;j--){if(dp2[i-j]>=j)break;dp2[i-j]=j;}}int ans=0;for(int i=1;i<=l-2;i++){if(dp1[i]&&dp2[i])ans=max(ans,dp1[i]+dp2[i]);}cout<<ans<<endl;
}