Codeforces Global Round 7 D2. Prefix-Suffix Palindrome (Hard version)（Manacher算法）

#include <bits/stdc++.h>
using namespace std;
string Manacher(const string &s){
    string t="#";
    for(char c:s) t+=c,t+="#";
    int RL[t.size()]={0};
    int MaxRight=0;
    int pos=0;
    for(int i=0;i<t.size();i++){
        if(i<MaxRight)
            RL[i]=min(RL[2*pos-i],MaxRight-i);
        else
            RL[i]=1;
        while(i-RL[i]>=0&&i+RL[i]<t.size()&&t[i-RL[i]]==t[i+RL[i]])
            RL[i]+=1;
        if(RL[i]+i-1>MaxRight)
            pos=i,MaxRight=RL[i]+i-1;
    }
    int MaxLen=0;
    for(int i=0;i<t.size();i++)
        if(RL[i]==i+1)
            MaxLen=i;
    return s.substr(0,MaxLen);
}
void solve(){
    string s;cin>>s;
    int l=0,r=s.size()-1;
    while(l<r&&s[l]==s[r]) ++l,--r;
    string s1=s.substr(l,r-l+1);
    string s2=s1;
    reverse(s2.begin(),s2.end());
    s1=Manacher(s1);
    s2=Manacher(s2);
    cout<<s.substr(0,l)<<(s1.size()>s2.size()?s1:s2)<<s.substr(r+1)<<"\n";
}
int main()
{
    int t;cin>>t;
    while(t--)
        solve();
    return 0;
}