Codeforces 1326D2. Prefix-Suffix Palindrome (Hard version)

#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=s; i<e; ++i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6 + 5;
int che[2*maxn];
string s,ma;
void manacher(string s,int len0){
    ma="$#"; rep(i,0,len0) ma+=s[i],ma+='#';
    // 别写成ma+=s[i]+'#';了 换成"#"应该就行 呜呜呜血泪教训
    int maxx=0,num=0,len=ma.size(); rep(i,0,len){
        che[i]=maxx>i?min(che[2*num-i],maxx-i):1;
        while(ma[i+che[i]]==ma[i-che[i]]) che[i]++;
        if(i+che[i]>maxx) maxx=i+che[i],num=i;
    }
}
void solve(){
    cin>>s; int l=0,r=s.size()-1;
    while(s[l]==s[r]&&l<r) l++,r--;
    string t1=s.substr(0,l),t2=s.substr(r+1);
    s=s.substr(l,r-l+1); manacher(s,s.size());
    int len=ma.size(),p(0),q(0),r1(0),r2(0);
    rep(i,0,len) if(p<che[i]&&i-che[i]<2) p=che[i],r1=i;
    dep(i,len-1,0) if(q<che[i]&&i+che[i]==len) q=che[i],r2=i;
    // 这部分比较考对manacher数组的熟练?hhh自己手写一下应该就行
    if(p>=q) cout<<t1+s.substr(0,p-1)+t2<<'\n';
    else cout<<t1+s.substr(s.size()-q+1)+t2<<'\n';
}
int main(){
    int _; sc(_); while(_--) solve();
}

#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=s; i<e; ++i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6 + 5;
string s; int n;
int seed,mod,hs1[maxn],hs2[maxn],bas[maxn]; // hs看情况开
void init(int* hs){
    s=' '+s; bas[0]=1; rep(i,1,n+1){
        bas[i]=1ll*bas[i-1]*seed%mod;
        hs[i]=1ll*hs[i-1]*seed%mod+s[i];
        if(hs[i]>=mod) hs[i]-=mod;
    } 
}
int getsum(int *h,int l,int r){
    int res=h[r]-1ll*h[l-1]*bas[r-l+1]%mod;
    if(res<0) res+=mod;
    return res;
}
void hash_init(){
    seed=?,mod=?; init(hs1);
    reverse(s.begin(),s.end()); init(hs2);
}
void solve(){
    cin>>s; int l=0,r=s.size()-1,p(0),q(0);
    while(s[l]==s[r]&&l<r) l++,r--;
    string t1=s.substr(0,l),t2=s.substr(r+1);
    s=s.substr(l,r-l+1); n=s.size(); hash_init();
    rep(i,1,n+1) if(getsum(hs1,1,i/2)==getsum(hs2,n-i+1,n-(i+1)/2)) p=i;
    rep(i,1,n+1) if(getsum(hs2,1,i/2)==getsum(hs1,n-i+1,n-(i+1)/2)) q=i;
    if(p>q){
        reverse(s.begin(),s.end());
        // 现在的s是' '+s+' ' 所以要从1开始
        cout<<t1+s.substr(1,p)+t2<<'\n';
    } else cout<<t1+s.substr(1,q)+t2<<'\n';
}
int main(){
    int _; sc(_); while(_--) solve();
}

#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=s; i<e; ++i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6 + 5;
string s;
struct PAM{
    struct node{
        int child[26],cnt,fail,num,len,pos;
    }tt[maxn];
    int last,n,tot;
    char s[maxn];
    inline void clear(){
        rep(i,0,tot+1){
            mst(tt[i].child,0);
            tt[i].cnt=tt[i].fail=tt[i].len=tt[i].num=tt[i].pos=0;
        } last=n=0; tt[0].fail=tot=1; tt[1].len=-1; 
    }
    inline int getfail(int x){
        while(s[n-tt[x].len-1]!=s[n]) x=tt[x].fail;
        return x;
    }
    inline void add(char ch){
        s[n]=ch;
        int cur=getfail(last);
        if(!tt[cur].child[ch-'a']){
            int now=++tot;
            tt[now].len=tt[cur].len+2;
            int p=getfail(tt[cur].fail);
            tt[now].fail=tt[p].child[ch-'a'];
            tt[cur].child[ch-'a']=now;
            tt[now].num=tt[tt[now].fail].num+1;
        }
        last=tt[n].pos=tt[cur].child[ch-'a'];
        ++tt[last].cnt; ++n;
    }
    inline void count(){
        dep(i,tot,0) tt[tt[i].fail].cnt+=tt[i].cnt;
    }
}pam;
int getpos(int n,int l,int r){
    int t=pam.tt[r].pos;
    while(l*2+pam.tt[t].len>n) t=pam.tt[t].fail;
    return pam.tt[t].len;
}
void solve(){
    cin>>s; int l=0,r=s.size()-1,n=s.size(),p(0),q(0);
    while(s[l]==s[r]&&l<r) l++,r--;
    pam.clear(); dep(i,n-1,0) pam.add(s[i]);
    p=getpos(n,l,r); reverse(s.begin(),s.end());
    pam.clear(); dep(i,n-1,0) pam.add(s[i]);
    q=getpos(n,l,r); reverse(s.begin(),s.end());
    if(max(p,q)+2*l>=n) cout<<s<<'\n';
    else if(p>q) cout<<s.substr(0,p+l)+s.substr(r+1)<<'\n';
    else cout<<s.substr(0,l)+s.substr(r-q+1)<<'\n';
}
int main(){
    int _; sc(_); while(_--) solve();
}

#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=s; i<e; ++i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 2e6 + 5;
int nex[maxn];
int getnext(string s){
    int i=0,j=-1,len=s.size();
    nex[0]=-1; while(i<len){
        if(j==-1||s[i]==s[j]){
            i++; j++; nex[i]=j;
        } else j=nex[j];
    } return nex[len];
}
void solve(){
    string s,t; cin>>s; int l=0,r=s.size()-1;
    while(s[l]==s[r]&&l<r) l++,r--;
    string t1=s.substr(0,l),t2=s.substr(r+1);
    s=s.substr(l,r-l+1); t=s; reverse(t.begin(),t.end());
    string a=s+'*'+t,b=t+'*'+s;
    string p=a.substr(0,getnext(a));
    string q=b.substr(0,getnext(b));
    cout<<t1<<(p.size()>q.size()?p:q)<<t2<<'\n';
}
int main(){
    int _; sc(_); while(_--) solve();
}