CF 1326 D. Prefix-Suffix Palindrome

D. Prefix-Suffix Palindrome

题意

给一个字符串 s，求一个字符串 t，t 由 s 的某个前缀以及某个后缀拼接而成，且 t 是回文串，长度不能超过 s。输出最长的 t

分析

建议先参考一下官方题解：http://codeforces.com/blog/entry/74961

先考虑 s 的最长border，即找最大的 l，使得 (s[1..l] = s[n-l+1...n].reverse()) , 可以想到 t 一定能够完全包含这两部分。

假如不包含，可以把它继续延长让它包含，比如abcxyzcba，最终答案一定包含abc以及cba两部分。

在求出最长的border之后，考虑剩余的中间部分，要找的就是最长回文前后缀，然后比较一下长度即可。

最长回文前缀如何求？可以回文自动机，可以马拉车，但也可以(KMP)。

前两种基本的是裸的做法，如果用(KMP)处理，则需要将串反过来接到后面（中间用特殊字符隔开），然后跑一边取nxt[2*len+1] 即可。

最长回文后缀就是将原串倒过来处理

KMP解法

#include <bits/stdc++.h>
using namespace std;
const int N = 2000010;
char s[N], t[N];
int nxt[N], n;
int getnxt(char *s, int n){
    nxt[1] = 0;
    for(int i = 2, j = 0; i <= n; i++){
        while(j > 0 && s[i] != s[j+1]) j = nxt[j];
        if(s[i] == s[j+1]) j++;
        nxt[i] = j;
    }
    return nxt[n];
}
int get(char *t, int len){
    t[len+1] = '#';
    for(int i = 1;i <= len; i++){
        t[i + len + 1] = t[len - i + 1];
    }
    return getnxt(t, 2*len + 1);
}
void print(int l, int r){
    for(int i=l;i<=r;i++)printf("%c", s[i]);
}
int main(){
    int T;scanf("%d", &T);
    while (T--)
    {
        scanf("%s", s+1);
        n = strlen(s + 1);
        int l = 0, r = n + 1;
        while(l + 1 < r - 1 && s[l + 1] == s[r - 1]) l++, r--;

        int len = 0;
        for(int i = l + 1; i <= r - 1; i++){
            t[++len] = s[i];
        }
        // 得到[l+1, r-1]区间的最长回文前缀
        int pre_len = get(t, len);
        reverse(t + 1, t + 1 + len);
        // 得到[l+1, r-1]区间的最长回文后缀
        int suf_len = get(t, len);

        print(1, l);
        if(pre_len > suf_len) print(l + 1, l+pre_len);
        else print(r - suf_len, r - 1);
        print(r, n);
        puts("");
    }
    return 0;
}

Manacher解法：

#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
int n;
char s[N], t[N];
char ma[N*2];
int mp[N*2];
int L[2*N], R[2*N], pre_len, suf_len;
//L[i] 表示以 i 为右端点的最长回文串长度，R[i]表示以 i 为左端点的最长回文长度
void Manacher(char s[], int len){
    int l = 0;
    ma[l++] = '$';
    ma[l++] = '#';
    for(int i=1; i <= len;i++){ // 填充字符串，注意s[i] 填到了 ma[i*2] 的位置
        ma[l++] = s[i];
        ma[l++] = '#';
    }
    ma[l] = 0;
    int mx = 0, id = 0;
    for(int i=0;i<l;i++){
        mp[i] = mx > i ? min(mp[2 * id - i], mx - i) : 1;
        while(ma[i + mp[i]] == ma[i - mp[i]]) mp[i] ++;
        if(i + mp[i] > mx){
            mx = i + mp[i];
            id = i;
        }
        if(mp[i] > 1){ // i+mp[i]-2以及 i-mp[i]+2 可以保证一定是原串字符对应的位置，而非特殊字符
            L[i + mp[i] - 2] = max(L[i + mp[i] - 2], mp[i] - 1);
            R[i - mp[i] + 2] = max(R[i - mp[i] + 2], mp[i] - 1);
        }
    }
    for(int i = 2; i < l; i += 2){ // i=2位置对应第一个原串字符，每次+2表示接着下一个原串字符
        R[i] = max(R[i], R[i - 2] - 2);
    }
    for(int i = l - 3; i >= 2; i -= 2){
        L[i] = max(L[i], L[i + 2] - 2);
    }
    pre_len = R[2]; // 取最长回文前缀长度
    suf_len = L[2*len]; // 取最长回文后缀长度
    for(int i=0;i<l;i++) L[i] = R[i] = 0;
}
void print(int l, int r){
    for(int i=l;i<=r;i++)printf("%c", s[i]);
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%s", s+1);
        n = strlen(s + 1);
        int l = 0, r = n + 1;
        while(l + 1 < r - 1 && s[l + 1] == s[r - 1]) l++, r--;
        int len = 0;
        for(int i = l + 1; i <= r - 1; i++){
            t[++len] = s[i];
        }
        t[len+1] = 0;
        
        Manacher(t, len);

        print(1, l);
        if(pre_len > suf_len) print(l + 1, l+pre_len);
        else print(r - suf_len, r - 1);
        print(r, n);
        puts("");
    }
}

回文自动机解法

const int N = 1000000 + 5;
int n;
char s[N], t[N], p[N];
struct PAT{
    int ch[N][26],fail[N],len[N],pos[N],tot,last;
    void init(){
        for(int i=0;i<=tot;i++){
            fail[i] = len[i] = 0;
            for(int j=0;j<26;j++)ch[i][j] = 0;
            pos[i] = 0;
        }
        s[0] = -1;fail[0] = 1;last = 0;
        len[0] = 0;len[1] = -1;tot = 1;
    }
    inline int newnode(int x){
        len[++tot] = x;return tot;
    }
    inline int getfail(char *s, int x,int n){
        while(s[n-len[x]-1] != s[n])x = fail[x];
        return x;
    }
    void create(char *s){
        s[0] = -1;
        for(int i=1;s[i];++i){
            int t = s[i] - 'a';
            int p = getfail(s, last,i);
            if(!ch[p][t]){
                int q = newnode(len[p]+2);
                fail[q] = ch[getfail(s, fail[p],i)][t];
                ch[p][t] = q;
            }

            pos[i] = ch[p][t];
            last = ch[p][t];
        }
    }
}pre, suf;
void print(int l, int r){
    for(int i=l;i<=r;i++)printf("%c", s[i]);
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        pre.init();
        suf.init();
        scanf("%s", s+1);
        n = strlen(s+1);
        
        int l = 0, r = n+1;
        while(s[l+1] == s[r-1] && l+1 < r-1) l++, r--;
        if(l == r - 1){
            print(1, n);
            puts("");
            continue;
        }
        int len = 0;
        for(int i=l+1;i<=r-1;i++){
            t[++len] = s[i];
        }
        t[len+1] = 0;
        for(int i=1;i<=len;i++){
            p[i] = t[len - i + 1];
        }
        p[len+1] = 0;
 
        pre.create(t);
        suf.create(p);

        if(pre.len[pre.pos[len]] > suf.len[suf.pos[len]]){
            print(1, l);
            print(r - pre.len[pre.pos[len]], n);
        }
        else{
            print(1, l + suf.len[suf.pos[len]]);
            print(r, n);
        }
 
        puts("");
    }
    return 0;
}