[国家集训队] 最长双回文串

题目大意

给定一个字符串 ss,求 ss 的最长双回文子串 tt,即可将 tt 分为两部分 xxyyx,  y1|x|, \; |y| \geqslant 1)且 xxyy 都是回文串。

2s100,0002 \leqslant |s| \leqslant 100,000

题目链接

【国家集训队】最长双回文串 - Luogu 4555

题解

求出 fromifrom_i 数组表示从 ii 开始的最长回文子串长,lastilast_i 表示在 ii 结尾的最长回文子串的长,答案即为 max(lasti+fromi+1)max(last_i + from_{i + 1})

考虑这两个数组的求法。用 Manacher 计算出 rir_i 数组,扫一遍 $r_i $数组,可以更新每个位置为中心的最长的回文子串的两头的两个数组的值;发现有 fromifromi11from_i \geqslant from_{i - 1} - 1lastilasti+11last_i \geqslant last_{i + 1} - 1,再扫一遍更新这两个数组的值。

最后枚举每一个在 Manacher 中添加的 # 字符,答案为 max(lasti+fromi),s[i]=#max(last_i + from_i), s'[i] = \#

代码

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
56
57
58
59
60
61
62
63
#include <cstdio>
#include <cstring>
#include <algorithm>
// #define DBG
const int MAXN = 100005;
char s[MAXN];
namespace Manacher {
int r[MAXN << 1], len;
char s[MAXN << 1];
void prepare() {
len = 0;
s[++len] = '@';
s[++len] = '#';
int n = strlen(::s);
for (int i = 0; i < n; i++) s[++len] = ::s[i], s[++len] = '#';
s[++len] = '\0';
}
void manacher() {
int right = 0, pos = 0;
for (int i = 1; i <= len; i++) {
int x = right < i ? 1 : std::min(r[2 * pos - i], right - i);
while (s[i + x] == s[i - x]) x++;
if (x + i > right) {
right = x + i;
pos = i;
}
r[i] = x;
}
}
void calc() {
prepare();
manacher();
}
}
int main() {
scanf("%s", s);
Manacher::calc();
static int from[MAXN << 1], last[MAXN << 1];
int *r = Manacher::r, len = Manacher::len;
#ifdef DBG
puts(Manacher::s + 1);
for (int i = 1; i <= len; i++) printf("pos: %d, r: %d\n", i, r[i]);
#endif
for (int i = 1; i <= len; i++) {
if (i - r[i] + 1 > 0) from[i - r[i] + 1] = std::max(from[i - r[i] + 1], r[i] - 1);
if (i + r[i] - 1 <= len) last[i + r[i] - 1] = std::max(last[i + r[i] - 1], r[i] - 1);
}
#ifdef DBG
puts(Manacher::s + 1);
for (int i = 1; i <= len; i++) printf("pos: %d, from: %d, last: %d\n", i, from[i], last[i]);
#endif
for (int i = 2; i <= len; i++) from[i] = std::max(from[i], from[i - 1] - 1);
for (int i = len - 1; i; i--) last[i] = std::max(last[i], last[i + 1] - 1);
#ifdef DBG
puts(Manacher::s + 1);
for (int i = 1; i <= len; i++) printf("pos: %d, from: %d, last: %d\n", i, from[i], last[i]);
#endif
int ans = 0;
for (int i = 1; i <= len; i++) if (Manacher::s[i] == '#')
ans = std::max(ans, last[i] + from[i]);
printf("%d\n", ans);
return 0;
}