求出最长的子串可以分成两个回文串
先处理出以每个位置为中心的最长回文子串，然后我是求了两个这样的数组left[] right[]，分别表示某位置往左最长的回文子串（以该位置结尾），右边的雷同
需要线性扫两遍。。。
处理这两个数组的时候细节问题整了半天，所幸最后还是整出来了。
[cpp]
#include
#include
#include
#include
using namespace std;
const int maxn= 200010;
namespace M {
int n;
struct node {
int a,b;
int cen;
node() {}
node(int _a,int _b):a(_a),b(_b){};
bool operator < (const node&cmp) const {
return b < cmp.b;
}
}in[maxn];
vector > P[maxn] ;
/// P[i]记录以i为中心的所有的最长回文子串（其实最多只有两个,奇偶性。。）
int left[maxn] , right[maxn];
bool ji[maxn];
void solve()
{
memset(ji,false,sizeof(ji));
int mx = 0;
for(int i = 0; i < n; i++)mx = max(mx,in[i].b);
for(int i = 1; i <= mx; i++) P[i].clear();
for(int i = 0; i < n; i++)
{
in[i].cen= in[i].a+in[i].b >> 1;
P[in[i].cen].push_back(make_pair(in[i].a,in[i].b));
}
int pt = 1;
for(int i = 1; i <= mx; i++)
{
for(; pt < i; pt++)
{
int a = P[pt][0].first;
int b = P[pt][0].second;
if(b>=i)
{
ji[i] = true;
break;
}
if(P[pt].size()==1) continue;
a = P[pt][1].first;
b = P[pt][1].second;
if(b>=i)
{
break;
}
}
left[i] = pt;
}
for(int i = 1; i <= mx; i++)
{
left[i] = max(1,(i - left[i])*2+ji[i]);
}
pt = mx;
memset(ji,false,sizeof(ji));
for(int i = mx; i >= 1; i--)
{
right[i] = i;
for(; pt >= i; pt--)
{
int a, b;
if(P[pt].size() > 1)
{
a = P[pt][1].first;
b = P[pt][1].second;
if(a<=i)
{
right[i] = pt + 1;
break;
}
}
a = P[pt][0].first;
b = P[pt][0].second;
if(a<=i)
{
right[i] = pt;
ji[i] = true;
break;
}
}
}
for(int i = 1; i <= mx; i++)
{
right[i] = max(1,(right[i] - i)*2+ji[i]);
}
int ans = 0;
for(int i = 1; i < mx; i++)
{
ans = max(ans,left[i]+right[i+1]);
}
printf("%d\n",ans);
}
}
struct Mancher {
char str[maxn];//start from index 1
int p[maxn];
char s[maxn];
int n;
void checkmax(int &ans,int b){
if(b>ans) ans=b;
}
inline int min(int a,int b){
return a }
void kp(){
int i;
int mx = 0;
int id;
for(i=1; i if( mx > i )
p[i] = min( p[2*id-i], p[id]+id-i );
else
p[i] = 1;
for(; str[i+p[i]] == str[i-p[i]]; p[i]++) ;
if( p[i] + i > mx ) {
mx = p[i] + i;
id = i;
}
}
}
void pre()
{
int i,j,k;
n = strlen(s);
str[0] = '$';
str[1] = '#';
for(i=0;i {
str[i*2 + 2] = s[i];
str[i*2 + 3] = '#';
}
n = n*2 + 2;