原文地址：http://www.cnblogs.com/GXZlegend/p/6802558.html
题目描述
顺序和逆序读起来完全一样的串叫做回文串。比如acbca是回文串，而abc不是（abc的顺序为“abc”，逆序为“cba”，不相同）。
输入长度为n的串S，求S的最长双回文子串T,即可将T分为两部分X，Y，（|X|,|Y|≥1）且X和Y都是回文串。
输入长度为n的串S，求S的最长双回文子串T,即可将T分为两部分X，Y，（|X|,|Y|≥1）且X和Y都是回文串。
输入
一行由小写英文字母组成的字符串S。
输出
一行一个整数，表示最长双回文子串的长度。
样例输入
baacaabbacabb
样例输出
12
题解
个人并不是擅长单调数据结构，于是用了Manacher后写了树状数组，稍微慢了点。
先求出以每个字符为中心的最大回文半径。
然后想办法求以某个字符结尾的最大回文半径，显然s[i]=i-min{j}+1，其中j≤i且j+p[j]-1≥i。
可以用树状数组维护j+p[j]-1≥i的最小的j，其中需要反过来减一下，因为树状数组是向下查询。
这样求出以某个字符结尾的最大回文半径，并得到最大回文长度。
之后同理求出以某个字符开头的最大回文长度。
最后一个向后一个向前加起来求一下就好了。
时间复杂度O(nlogn)，存在更优秀的O(n)算法，参考CQzhangyu's blog。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 2000010
using namespace std;
int p[N] , f[N] , s1[N] , s2[N] , n;
char str[N] , tmp[N];
void update1(int x , int a)
{
int i;
for(i = x ; i <= n ; i += i & -i) f[i] = min(f[i] , a);
}
void update2(int x , int a)
{
int i;
for(i = x ; i <= n ; i += i & -i) f[i] = max(f[i] , a);
}
int query1(int x)
{
int i , ans = 0x7f7f7f7f;
for(i = x ; i ; i -= i & -i) ans = min(ans , f[i]);
return ans;
}
int query2(int x)
{
int i , ans = 0;
for(i = x ; i ; i -= i & -i) ans = max(ans , f[i]);
return ans;
}
int main()
{
int i , mx = 0 , last = 0 , ans = 0;
scanf("%s" , str + 1) , n = strlen(str + 1);
tmp[0] = '0';
for(i = 1 ; i <= n ; i ++ ) tmp[i * 2 - 1] = '#' , tmp[i * 2] = str[i];
n = n * 2 + 1 , tmp[n] = '#';
for(i = 1 ; i <= n ; i ++ )
{
if(mx >= i) p[i] = min(p[last * 2 - i] , mx - i + 1);
else p[i] = 1;
while(tmp[i - p[i]] == tmp[i + p[i]]) p[i] ++ ;
if(mx < i + p[i] - 1) mx = i + p[i] - 1 , last = i;
}
memset(f , 0x7f , sizeof(f));
for(i = 1 ; i <= n ; i ++ )
update1(n - (i + p[i] - 1) + 1 , i) , s1[i] = 2 * i - 2 * query1(n - i + 1) + 1;
memset(f , 0 , sizeof(f));
for(i = n ; i >= 1 ; i -- )
update2(i - p[i] + 1 , i) , s2[i] = 2 * query2(i) - 2 * i + 1;
for(i = 2 ; i <= n ; i ++ ) ans = max(ans , (s1[i - 1] + s2[i]) / 2);
printf("%d
" , ans);
return 0;
}