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

发表于2017-04-24更新于2020-08-06

题目大意

给定一个字符串 ss，求 ss 的最长双回文子串 tt，即可将 tt 分为两部分 xx、yy（∣x∣,  ∣y∣⩾1|x|, \; |y| \geqslant 1）且 xx 和 yy 都是回文串。

2⩽∣s∣⩽100,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 $数组，可以更新每个位置为中心的最长的回文子串的两头的两个数组的值；发现有 fromi⩾fromi−1−1from_i \geqslant from_{i - 1} - 1、lasti⩾lasti+1−1last_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;
}