28分求助
查看原帖
28分求助
413065
xiezheyuan楼主2023/2/8 13:03
#include <bits/stdc++.h>
using namespace std;

const int N = 5e5+5;

string pre(string s){
    if(s.size()==0) return "^$";
    string ret="^";
    for(int i=0;i<s.size();i++){ret+='#';ret+=s[i];}
    return ret+="#$";
}

int p[N],L[N],R[N];

int manacher(string str){
    int n=str.size(),c=0,r=0,ans=0;
    for(int i=1;i<n-1;i++){
        int j=(c<<1)-i;
        if(r>i) p[i]=min(r-i,p[j]);
        else {p[i]=0;}
        while(str[i+p[i]+1]==str[i-p[i]-1]) p[i]++;
        if(i+p[i]>r){c=i;r=i+p[i];}
        L[i+p[i]-1]=max(L[i+p[i]-1],p[i]-1);
        R[i-p[i]+1]=max(R[i-p[i]+1],p[i]-1);
    }
    for(int i=2;i<n-1;i+=2) R[i]=max(R[i],R[i-2]-2);
    for(int i=n-2;i>=2;i-=2) L[i]=max(L[i],L[i+2]-2);
    for(int i=2;i<n-1;i+=2){
    	if(R[i]&&L[i]) ans=max(ans,L[i]+R[i]);
	}
    return ans;
}

string str;

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>str;
    cout<<manacher(pre(str));
    return 0;
}
2023/2/8 13:03
加载中...