Skip to content

洛谷 - P4555 最长双回文串

检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

#题面

#题目描述

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

输入长度为 nn 的串 SS,求 SS 的最长双回文子串 TT,即可将 TT 分为两部分 X,YX, Y1X,Y1 \leq |X|,|Y|)且 XXYY 都是回文串。

#输入格式

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

#输出格式

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

#输入输出样例

样例输入 #1

baacaabbacabb

样例输出 #1

12

样例解释 #1

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

#数据范围与约定

对于 100%100\% 的数据,2S1052 \leq |S| \leq 10^5

#思路

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

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

li+(pi1)=max(li+(pi1),pi1)ri(pi1)=max(ri(pi1),pi1)\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,li22)ri=max(ri,ri+22)\begin{aligned} l_i = \max(l_i, l_{i - 2} - 2) \\ r_i = \max(r_i, r_{i + 2} - 2) \\ \end{aligned}

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

#代码

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