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
样例说明
从第二个字符开始的字符串aacaabbacabb可分为aacaa与bbacabb两部分，且两者都是回文串。
对于100%的数据，2≤|S|≤10^5
2015.4.25新加数据一组
题解
马拉车+一个辣鸡Dp
回文串你都想不到马拉车？那就来caioj学吧哈哈哈哈。。
对原串跑一遍马拉车，顺便对原串预处理出来一个lef和rig数组
lef[i]表示i左边最长回文串的p数组,rig[i]表示i右边最长回文串的p数组，其中这两个回文串的边界都要是i
求出来后枚举断点求答案就好了。
至于如何求lef[i]? 先用p数组求一边大概的lef，然后lef[i]=max(lef[i],lef[i+1]-1)dp一下
rig也是同理
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
char s[2110000],now[2110000];
int p[2110000],len,tmp[2110000][2];
int lef[2110000],rig[2110000];//向左 向右延伸的最长回文长度
void manacher()
{len=strlen(s+1);for(int i=1;i<=len;i++)now[2*i-1]='#',now[2*i]=s[i];len=2*len+1;now[len]='#';int pos=0,R=0;for(int i=1;i<=len;i++){int j=2*pos-i;if(i<=R)p[i]=min(p[j],R-i);else p[i]=1;while(1<=i-p[i] && i+p[i]<=len && now[i-p[i]]==now[i+p[i]])p[i]++;if(i+p[i]-1>R)pos=i,R=i+p[i]-1;}for(int i=1;i<=len;i++)tmp[i][0]=i-p[i]+1,tmp[i][1]=i+p[i]-1;for(int i=1;i<=len;i++)rig[tmp[i][0]]=max(rig[tmp[i][0]],p[i]),lef[tmp[i][1]]=max(lef[tmp[i][1]],p[i]);for(int i=len-1;i>=1;i--)lef[i]=max(lef[i],lef[i+1]-1);for(int i=2;i<=len;i++)rig[i]=max(rig[i],rig[i-1]-1);
}
int n;
int main()
{scanf("%d",&n);scanf("%s",s+1);manacher();int ans=0;for(int i=1;i<=len;i++)ans=max(ans,lef[i]-1+rig[i]-1);printf("%d\n",ans);return 0;
}