[国家集训队] 最长双回文串

原来每个点开始和结束的回文串长度是可以线性计算出的
（我以前一直都用线段树（捂脸）

#include <bits/stdc++.h>
using namespace std;

namespace man {
const int N = 11000005;
char str[N], s[N<<1];
int a[N<<1];

int manacher(int len){
    a[0] = 0;
    int ans = 0, j;
    for(int i = 0; i < len; ){
        while(i-a[i]>0 && s[i+a[i]+1]==s[i-a[i]-1])
              a[i]++;
        if(ans < a[i])ans = a[i];
        j = i+1;
        while(j<=i+a[i] && i-a[i]!=i+i-j-a[i+i-j]){
            a[j] = min(a[i+i-j], i+a[i]-j);
            j++;
        }
        a[j] = max(i+a[i]-j, 0);
        i = j;
    }
    return ans;
}

int solve(){
    int len;
    len = 2*strlen(str)+1;
    for(int i = 0; str[i] != ''; i++){
        s[i+i] = '';
        s[i+i+1] = str[i];
    }
    s[len-1] = '';
    return manacher(len);
}
}

using man::str;
using man::a;
using man::N;

int l[N],r[N];

int main() {
    cin>>str;
    int n=strlen(str);
    man::solve();
    for(int i=0;i<=2*n;i++) {
        l[i-a[i]+1]=max(l[i-a[i]+1],a[i]);
        r[i+a[i]-1]=max(r[i+a[i]-1],a[i]);
    }
    for(int i=2;i<=2*n;i++) {
        l[i]=max(l[i],l[i-2]-2);
    }
    for(int i=0;i<=2*n;i++) {
        r[i]=max(r[i],r[i+2]-2);
    }
    int ans=0;
    for(int i=2;i<=2*n;i++) 
        if(r[i-1]&&l[i+1]) ans=max(ans,r[i-1]+l[i+1]);
    cout<<ans;
}