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

Raw Download Revise
#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;

}