CodeForces-1326D Prefix-Suffix Palindrome

传送门：CodeForces-1326D

思路分析

找一个由前缀+后缀组成的最大回文串
先找前后缀共同的回文部分，这样问题就变为前缀+回文+后缀了
我们只需要对去除前后缀之后的字符串进行处理了
设这个字符串为S，找最长前缀（后缀）回文串，接下来有三种处理方法，见代码部分

样例输入

5
a
abcdfdcecba
abbaxyzyx
codeforces
acbba

样例输出

a
abcdfdcba
xyzyx
c
abba

hash代码

对S和S的反串进行hash处理，然后枚举前后缀串中最大的回文串，hash是$O(1)$判断

#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <vector>
#include <string>
#include <cstdio>
#include <chrono>
#include <random>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls x<<1
#define rs x<<1|1
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define lowbit(x) x&(-x)
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int INF = 0x3f3f3f3f;
const int base= 10001659;
const int mod=100000429;
const int N=1e6+10;

int n;
ll ba[N],hash1[N],hash2[N];

void init(string &s,ll *ha) {
    s="#"+s;
    ba[0]=1;
    for(int i=1; i<=n; i++) {
        ba[i]=ba[i-1]*base%mod;
        ha[i]=(ha[i-1]*base)%mod+s[i];
    }
}

ll getkey(ll *ha,int l,int r) {
    ll ans=(ha[r]-ha[l-1]*ba[r-l+1]+mod)%mod;
    if(ans<0) ans+=mod;
    return ans;
}

int main() {
    IOS;
#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif

    int t;
    cin>>t;
    while(t--) {
        string s;
        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);
        n=s.size();

        init(s,hash1);
        reverse(all(s));
        init(s,hash2);

        int pos1=0,pos2=0;
        for(int i=1; i<=n; i++) if(getkey(hash1,1,i/2)==getkey(hash2,n-i+1,n-(i+1)/2)) pos1=i;
        for(int i=1; i<=n; i++) if(getkey(hash2,1,i/2)==getkey(hash1,n-i+1,n-(i+1)/2)) pos2=i;

        if(pos1>pos2) {
            reverse(all(s));
            cout<<t1<<s.substr(1,pos1)<<t2<<endl;
        } else {
            cout<<t1<<s.substr(1,pos2)<<t2<<endl;
        }
    }



    return 0;
}

manacher代码

对S串进行manacher处理，枚举以每个点为对称点的最大回文串，要满足前缀（后缀）关系，即从1开头或者len结尾
注意manacher数组与原数组之间的关系

#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <vector>
#include <string>
#include <cstdio>
#include <chrono>
#include <random>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls x<<1
#define rs x<<1|1
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define sz(x) x.size()
#define lowbit(x) x&(-x)
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int INF = 0x3f3f3f3f;
const int N=1e6+10;

int che[N<<1];

void manacher(string s,string &ma) {
    ma="$#";
    for(int i=0; i<sz(s); i++) ma+=s[i],ma+='#';
    int maxn=0,num=0,len=sz(ma);
    for(int i=0; i<len; i++) {
        che[i]=maxn>i?min(che[2*num-i],maxn-i):1;
        while(ma[i+che[i]]==ma[i-che[i]]) che[i]++;
        if(i+che[i]>maxn) maxn=i+che[i],num=i;
    }
}

int main() {
    IOS;
#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif

    int t;
    cin>>t;
    while(t--) {
        string s;
        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);

        string ma;
        manacher(s,ma);

        int len=sz(ma);
        int r1=0,pos1=0,r2=0,pos2=0;
        for(int i=0; i<len; i++) if(r1<che[i] && i-che[i]<2) r1=che[i],pos1=i;
        for(int i=len-1; i>=0; i--) if(r2<che[i] && i+che[i]==len) r2=che[i],pos2=i;
            
        if(r1>r2) cout<<t1+s.substr(0,r1-1)+t2<<endl;
        else cout<<t1+s.substr(sz(s)+1-r2)+t2<<endl;
    }


    return 0;
}

kmp代码

我们知道kmp中的next数组的含义：next[i]表示前i字符串中，最长的相同前缀后缀
将S与它的反串相连，那么这个相同的前缀后缀就等于S的最长前缀回文，因为这个长度不能超过S的长度
所以拼接的时候再中间加个不相关的字符中断，防止出现溢出的情况

#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <vector>
#include <string>
#include <cstdio>
#include <chrono>
#include <random>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls x<<1
#define rs x<<1|1
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define lowbit(x) x&(-x)
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int INF = 0x3f3f3f3f;
const int base= 67;
const int mod=1e9+7;
const int N=1e6+10;

int n,nex[N<<1];

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];
}


int main() {
    IOS;
#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif

    int t;
    cin>>t;
    while(t--) {
        string s;
        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);
        
        string t=s;
        reverse(all(t));
        string a=s+"#"+t,b=t+"#"+s;
        int pos1=getnext(a);
        int pos2=getnext(b);

        if(pos1>pos2) cout<<t1+a.substr(0,pos1)+t2<<endl;
        else cout<<t1+b.substr(0,pos2)+t2<<endl;

    }



    return 0;
}