题解 CF1326D2 【Prefix-Suffix Palindrome (Hard version)】

显然可以先贪心地取互为反串的最长前后缀。

取完扔掉之后，相当于要在剩下的字符串的前缀或后缀找到一个最长的回文串。

manacher 即可，时间复杂度 \mathcal O(n)。

const int N = 1e6 + 7;
int n, m;
char s[N], t[N];

inline int work(char *s, int n) {
    string ss = "$#";
    vi p;
    for (int i = 1; i <= n; i++) ss += s[i], ss += "#";
    p.pb(1);
    int mx = 0, id = 0, ans = 1;
    for (int i = 1; i < (int)ss.length(); i++) {
        p.pb(mx > i ? min(p[2*id-i], mx - i) : 1);
        while (i + p[i] < (int)ss.length() && ss[i+p[i]] == ss[i-p[i]]) ++p[i];
        if (i == p[i]) ans = max(ans, p[i]);
        if (i + p[i] > mx) mx = i + p[i], id = i;
    }
    return ans - 1;
}

inline void solve() {
    rds(s, n);
    int p = 1;
    while (p <= n && s[p] == s[n+1-p]) ++p;
    if (p == n + 1) {
        for (int i = 1; i <= n; i++) putchar(s[i]);
        return puts(""), void();
    }
    m = 0;
    for (int i = p; i <= n + 1 - p; i++) t[++m] = s[i];
    int l = work(t, m);
    reverse(t + 1, t + m + 1);
    int r = work(t, m);
    reverse(t + 1, t + m + 1);
    if (l < r) reverse(t + 1, t + m + 1), swap(l, r);
    for (int i = 1; i < p; i++) putchar(s[i]);
    for (int i = 1; i <= l; i++) putchar(t[i]);
    for (int i = p - 1; i; i--) putchar(s[i]);
    puts("");
}

int main() {
    int T;
    rd(T);
    while (T--) solve();
    return 0;
}