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] 即可。

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

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

CF 1326 D. Prefix-Suffix Palindrome

原文：https://www.cnblogs.com/1625--H/p/12531494.html