مسئلة قحبة تانى

#include <bits/stdc++.h>
using namespace std;
#define ld long double
#define F first
#define S second
#define Lnode 2*node+1
#define Rnode 2*node+2
#define MID (l+r>>1)
#define el '\n'
#define coutf(x) for(auto v:(x)) cout<<v<<' '; cout<<el
#define coutp(x) for(auto v:(x)) cout<<v.F<<' '<<v.S<<el
#define cinl(x) for(auto &v:(x)) cin>>v;
#define all(x)  x.begin(),x.end()
#define ll long long
#define sz(x)  (int)x.size()
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define vi vector<ll>
using ull = unsigned long long;
vector<int>lcp (const string& s)
{
    int n=s.size();
    vector<int>phi(n,0);
    for (int i=1,k=0;i<n;i++)
    {
        k=phi[i-1];
        while (k>0&&s[i]!=s[k])k=phi[k-1];
        if (s[i]==s[k])k++;
        phi[i]=k;
    }
    return phi;

}

pi mancher(const string&s)
{
    int c=0,r=0;
    string t="#";
    for (auto it:s)t+=it,t+="#";
    // for (auto it:t)cout<<it<<" ";
    int n=t.size();
    vector<int>p(n,0);
    for (int i=0;i<n;i++){
        if (i<r)
        {
            int miror = 2*c-i;
            p[i]=min(r-i,p[miror]);
        }
        int left=i-p[i]-1;
        int right=i+p[i]+1;
        while (left>=0&&right<n&&t[left]==t[right])right++,left--,p[i]++;
        if (i+p[i]>r)r=i+p[i],c=i;
    }
    int mxlen=0,mx=0;
    for (int i=1;i<n-1;i++)
    {

        if (p[i]>mx)
        {
            if ((i-p[i])/2<=0||((i-p[i])/2)+p[i]>=s.size())
            {

            mx=p[i];
            mxlen=i;
            }
        }
    }
    int start=(mxlen-mx)/2;
    return {start,mx};
}
void solve()
{
string s;
    cin>>s;
    string  rev1=s;
    string ss=s;
    string rev=s;
    reverse(all(rev));
    rev+="#"+s;
    reverse(all(rev1));
    s+="#"+rev1;

    auto pref=lcp(rev);
    int ps=0;
    for (int i=rev.size()/2+1;i<rev.size()&&pref[i];i++)ps=max(ps,pref[i]);
    int mxs=pref[rev.size()-1];
    auto pref2=lcp(s);
    int mxp=pref2[s.size()-1];


    string ns=ss.substr(ps,ss.size()-(2*ps));
    auto pal=mancher(ns);
    string ans="";

    ans+=ss.substr(0,ps);
    ans+=ns.substr(pal.first,pal.second);
    if (2*ps<=ss.size())
    ans+=ss.substr(ss.size()-ps,ps);


    string prefix=s.substr(0,mxp);
    string suffix=s.substr(ss.size()-mxs,mxs);

    if (ans.size()>prefix.size()){

        if (ans.size()>suffix.size())cout<<ans<<"\n";
        else cout<<suffix<<"\n";
    }
    else if (prefix.size()>suffix.size())cout<<prefix<<"\n";
    else
        cout<<suffix<<"\n";


}

int32_t main() {
    #ifndef ONLINE_JUDGE
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #endif

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int tc=1;
   cin>>tc;
    for (int i=1;i<=tc;i++){solve();}
    return 0;
}