洛谷 - P4555 最长双回文串

题面

题目描述

顺序和逆序读起来完全一样的串叫做回文串。比如 acbca 是回文串，而 abc 不是（abc 的顺序为 abc，逆序为 cba，不相同）。

输入长度为 $n$ 的串 $S$，求 $S$ 的最长双回文子串 $T$,即可将 $T$ 分为两部分 $X, Y$（$1 \leq |X|,|Y|$）且 $X$ 和 $Y$ 都是回文串。

输入格式

一行由小写英文字母组成的字符串 $S$。

输出格式

一行一个整数，表示最长双回文子串的长度。

输入输出样例

样例输入 #1

baacaabbacabb

样例输出 #1

12

样例解释 #1

从第二个字符开始的字符串 aacaabbacabb 可分为 aacaa 与 bbacabb 两部分，且两者都是回文串。

数据范围与约定

对于 $100\%$ 的数据，$2 \leq |S| \leq 10^5$。

思路

刚拿到这道题的时候，一下子有了一个偏朴素的做法：先跑一遍 Manacher，然后对于每个点分别枚举以它为左右端点的回文串相加取最大值。又去看了眼数据范围，仔细一想发现这个做法实际复杂度是 $O(n^2)$ 的，无法通过本题。

可以设 $l_i$ 表示以 $i$ 为左端点的最长的回文串，$r_i$ 表示以 $i$ 为右端点的最长的回文串。有转移方程如下：

$$\begin{aligned} l_{i + (p_i - 1)} &= \max(l_{i + (p_i - 1)}, p_i - 1) \\ r_{i - (p_i - 1)} &= \max(r_{i - (p_i - 1)}, p_i - 1) \\ \end{aligned}$$

然后再递推将前/后方的最长回文串转移过来。因为两个回文串不能重叠，所以每次选择分隔符 # 进行枚举，就避免了重叠的问题，转移方程如下：

$$\begin{aligned} l_i = \max(l_i, l_{i - 2} - 2) \\ r_i = \max(r_i, r_{i + 2} - 2) \\ \end{aligned}$$

之后再次枚举每个断点更新答案即可。

代码

#include <iostream>
#include <string>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 1e5 + 5;

int mid, r, p[N << 1], a[N << 1], b[N << 1], ans;
std::string s1, s2;

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> s1;

    s2.push_back('^');

    for (const char &c : s1) {
        s2.push_back('#');
        s2.push_back(c);
    }

    s2 += "#$";

    for (int i = 1; i < s2.size(); i++) {
        p[i] = i < r ? std::min(p[mid * 2 - i], r - i) : 1;
        while (s2[i - p[i]] == s2[i + p[i]]) p[i]++;
        if (i + p[i] > r) {
            r = i + p[i];
            mid = i;
        }

        a[i + p[i] - 1] = std::max(a[i + p[i] - 1], p[i] - 1);
        b[i - p[i] + 1] = std::max(b[i - p[i] + 1], p[i] - 1);
    }

    for (int i = s2.size() - 4; i >= 3; i -= 2) {
        a[i] = std::max(a[i], a[i + 2] - 2);
    }

    for (int i = 3; i <= s2.size() - 4; i += 2) {
        b[i] = std::max(b[i], b[i - 2] - 2);
    }

    for (int i = 3; i <= s2.size() - 4; i += 2) {
        ans = std::max(ans, a[i] + b[i]);
    }

    cout << ans << endl;

    return 0;
}