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

显然可以想到用manacher

然后统计一下每个位置开头和结尾的最长子序列

但是怎么更新？边跑mancher边更新每一个位置太慢了

那就到最后递推更新呗。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
template<class T>
void read(T &now){
    now=0;
    char c=getchar();
    int f=1;
    while((!isdigit(c))){
        if(c=='-') f=-1;
    //  cout<<isdigit(c)<<" "<<c<<" ";
        c=getchar();
    }
    while(isdigit(c)){
        now=(now<<1)+(now<<3)+c-'0';
        c=getchar();
    }
    now*=f;
}
int r[10000001];
int ll[10000001];
int p[10000001];
int mid;
int rr;
string s,ss;
int main(){
    cin>>ss;
    int l=ss.length();
    s+=' ';
    s+='$';
    for(int i=0;i<l;++i){
        if(ss[i]=='\n'&&s[i+1]=='\r')
        break;
        s+=ss[i];
        s+='$';
    }
    l=s.length()-1;
    int mid=0;
    for(int i=1;i<=l;++i){
        if(i<=rr&&mid*2-i>0){
            p[i]=min(rr-i-1,p[mid*2-i]);
        }
        while(i+p[i]<=l&&i-p[i]>0&&s[i+p[i]]==s[i-p[i]]){
            p[i]++;
        }
        if(i+p[i]-1>rr){
            rr=i+p[i]-1;
            mid=i;
        }
        r[i+p[i]-1]=max(r[i+p[i]-1],p[i]-1);
        ll[i-p[i]+1]=max(ll[i-p[i]+1],p[i]-1);
    }
    for(int i=2;i<=l;++i){
        ll[i]=max(ll[i],ll[i-2]-2);
    }
    for(int i=l-1;i>=2;--i){
        r[i]=max(r[i],r[i+2]-2);
    }
    int ans=0;
    for(int i=1;i<=l;i+=2){
        if(ll[i]!=0&&r[i]!=0)
        ans=max(ans,ll[i]+r[i]);
    }
    cout<<ans;
    return 0;
}