Skip to content

洛谷 - P4555 最长双回文串

题解784 字
# 洛谷 # 字符串 # 国家集训队 # Manacher
检测到 KaTeX 加载失败，可能会导致文中的数学公式无法正常渲染。

#题面

#题目描述

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

输入长度为 nn 的串 SS，求 SS 的最长双回文子串 TT,即可将 TT 分为两部分 X,YX, Y（1≤∣X∣,∣Y∣1 \leq |X|,|Y|）且 XX 和 YY 都是回文串。

#输入格式

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

#输出格式

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

#输入输出样例

样例输入 #1

baacaabbacabb

样例输出 #1

12

样例解释 #1

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

#数据范围与约定

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

#思路

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

可以设 lil_i 表示以 ii 为左端点的最长的回文串，rir_i 表示以 ii 为右端点的最长的回文串。有转移方程如下：

li+(pi−1)=max⁡(li+(pi−1),pi−1)ri−(pi−1)=max⁡(ri−(pi−1),pi−1)\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}

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

li=max⁡(li,li−2−2)ri=max⁡(ri,ri+2−2)\begin{aligned} l_i = \max(l_i, l_{i - 2} - 2) \\ r_i = \max(r_i, r_{i + 2} - 2) \\ \end{aligned}

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

#代码

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#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;
}