usaco-1.3.3 最长的回文

形式化题目

给定一个长度不超过 $20\,000$ 的原始字符串 $S$ 。定义“有效字符”为大小写英文字母。将 $S$ 中出现的所有有效字符提取出来，统一转换为小写后按原相对顺序拼接为纯字母串 $T$ ，并记录每个字母在原串 $S$ 中的下标映射 $\text{pos}$ 。

要求寻找 $T$ 中的一个最长回文连续子串 $T[l \dots r]$ ：

第一行输出该回文子串的字母长度 $r - l + 1$ 。
第二行及后续输出原串中从 $\text{pos}[l]$ 到 $\text{pos}[r]$ 的完整子串 $S[\text{pos}[l] \dots \text{pos}[r]]$ （保留所有的非字母字符与换行格式）。
若存在多个长度相同的最长回文子串，选择在 $T$ 中起始位置最靠前的一个。

正解

思路

本题的核心任务是在忽略大小写和标点符号的前提下求最长回文子串，并将结果还原至原文本。

1. 字符提取与下标映射

由于最终输出要求保留原始文本中的空格、标点符号及换行符，我们先遍历原字符串 $S$ ，提取出所有英文字母并统一转为小写，同时记录每个字母在原串中的下标：

T[k] = \operatorname{lower}(S[\text{pos}[k]])

这样，如果在

T

中找到了一个回文子串

T[l \dots r]

，它在原串中对应的完整子串就是

S[\text{pos}[l] \dots \text{pos}[r]]

，长度为

r - l + 1

。

2. 从朴素中心扩展到 Manacher 算法

如果使用朴素的中心扩展法：枚举每一个可能的对称中心向两边拓展，时间复杂度为 $O(|T|^2)$ 。在最坏情况下操作次数约为 $(20\,000)^2 / 2 \approx 2 \times 10^8$ ，对于 Python 来说很容易面临超时风险。

我们采用 Manacher 算法（马拉车算法），在 $O(|T|)$ 线性时间内求解：

插空统一奇偶回文：在 $T$ 的每两个字符之间以及头尾插入分隔符 #，并在两侧添加不出现的边界哨兵 ^ 与 $（例如串 aba 转化为 ^#a#b#a#$）。如此一来，所有回文子串在新串中均转化为以某个字符为中心的奇回文。
利用对称性加速：维护当前已探测到的回文串能覆盖到的最右边界 $R$ 及其对称中心 $C$ 。当遍历到位置 $i$ 时：
- 若 $i < R$ ，设 $i$ 关于 $C$ 的对称位置为 $i' = 2C - i$ 。由于以 $C$ 为中心的回文串性质， $i$ 处的初始回文半径至少为 $\min(R - i, P[i'])$ 。
- 随后再从该半径处开始向两边扩展，暴力比较字符。
- 扩展结束后，若 $i + P[i] > R$ ，则更新 $C = i, R = i + P[i]$ 。
映射与还原：在新构造的串中，以 $i$ 为中心的最大回文半径 $P[i]$ 正好等于原字母串 $T$ 中对应回文子串的字母长度；而在 $T$ 中的起始下标正好为 $(i - P[i]) // 2$ 。

在扫描更新最优解时，使用严格大于判定 p[i] > max_len，从而保证在出现相同最长长度时输出最先出现的回文。

代码

Python 版：

python

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-04-18 10:00
# update_at: 2026-04-18 10:00

import sys


def find_longest_palindrome(letters: str) -> tuple[int, int, int]:
    """用 Manacher 算法计算最长回文子串在字母串中的 (长度, 起始下标, 结束下标)。"""
    t = "^#" + "#".join(letters) + "#$"
    p = [0] * len(t)
    center = right = 0
    max_len = 0
    best_start = 0

    for i in range(1, len(t) - 1):
        p[i] = min(right - i, p[2 * center - i]) if right > i else 0
        while t[i + 1 + p[i]] == t[i - 1 - p[i]]:
            p[i] += 1
        if i + p[i] > right:
            center, right = i, i + p[i]
        # p[i] 即为原字母串中以相应中心为核心的回文半径/长度
        if p[i] > max_len:
            max_len = p[i]
            best_start = (i - p[i]) // 2  # 映射回 letters 中的起始下标

    return max_len, best_start, best_start + max_len - 1


def solve() -> None:
    raw = sys.stdin.read()
    if not raw:
        return

    # 提取所有字母及其在原始文本中的索引，统一转小写进行匹配
    indexed_letters = [(ch.lower(), idx) for idx, ch in enumerate(raw) if ch.isalpha()]
    if not indexed_letters:
        print(0)
        return

    clean_chars = "".join(ch for ch, _ in indexed_letters)
    max_len, l_idx, r_idx = find_longest_palindrome(clean_chars)

    orig_start = indexed_letters[l_idx][1]
    orig_end = indexed_letters[r_idx][1]

    print(max_len)
    print(raw[orig_start : orig_end + 1])


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 09:12
 * update_at: 2026-10-06 09:12
 */
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 20005;         // 原始文本长度上限
const int MAXM = 2 * MAXN + 5;  // Manacher 插字符后的串长上限

char raw[MAXN];       // 原始文本，按读入顺序保存（含空格、标点、换行）
int raw_len;
char letter[MAXN];    // 过滤出的纯字母串，统一转小写
int pos[MAXN];        // pos[k] = letter[k] 在 raw 中的下标
int letter_cnt;

char t[MAXM];         // 插入 '#' 分隔符后的 Manacher 串，两端放哨兵 '^' 与 '$'
int p[MAXM];          // p[i] = 以 t[i] 为中心的回文半径

// 把纯字母串插成 ^#a#b#...#$ 的形式，返回新串长度。
int build_manacher_string() {
    int n = 0;
    t[n++] = '^';
    for (int i = 0; i < letter_cnt; i++) {
        t[n++] = '#';
        t[n++] = letter[i];
    }
    t[n++] = '#';
    t[n++] = '$';
    return n;
}

// 在字母串上跑 Manacher，返回最长回文长度，并写回字母串中的起止下标。
int manacher(int &best_l, int &best_r) {
    int m = build_manacher_string();
    p[0] = 0;  // p[0] 对应哨兵 '^'，不会被访问
    int center = 0;  // 当前回文覆盖最右的对称中心
    int right = 0;   // 当前回文覆盖到的最右边界
    int max_len = 0;
    int best_start = 0;

    for (int i = 1; i < m - 1; i++) {
        if (i < right) {
            // 利用对称性取初始半径，再暴力向两边扩展
            int mirror = 2 * center - i;
            p[i] = min(right - i, p[mirror]);
        } else {
            p[i] = 0;
        }
        while (t[i + 1 + p[i]] == t[i - 1 - p[i]]) {
            p[i]++;
        }
        if (i + p[i] > right) {
            center = i;
            right = i + p[i];
        }
        // 严格大于保证等长时取字母串中最靠前的回文
        if (p[i] > max_len) {
            max_len = p[i];
            best_start = (i - p[i]) / 2;  // 映射回字母串中的起始下标
        }
    }
    best_l = best_start;
    best_r = best_start + max_len - 1;
    return max_len;
}

void solve() {
    char ch;
    while (raw_len < MAXN - 1 && cin.get(ch)) {
        raw[raw_len++] = ch;
    }

    // 提取字母并记录其在原始文本中的下标，字母统一转小写用于匹配
    for (int i = 0; i < raw_len; i++) {
        if ((raw[i] >= 'A' && raw[i] <= 'Z') || (raw[i] >= 'a' && raw[i] <= 'z')) {
            char c = raw[i];
            if (c >= 'A' && c <= 'Z') {
                c = c - 'A' + 'a';
            }
            letter[letter_cnt] = c;
            pos[letter_cnt] = i;
            letter_cnt++;
        }
    }

    if (letter_cnt == 0) {
        cout << 0 << "\n";
        return;
    }

    int best_l = 0;
    int best_r = 0;
    int max_len = manacher(best_l, best_r);

    int out_start = pos[best_l];
    int out_end = pos[best_r];
    cout << max_len << "\n";
    cout.write(raw + out_start, out_end - out_start + 1);
    cout << "\n";
}

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

    solve();

    return 0;
}

复杂度

时间复杂度： $O(N)$ 。提取有效字母需遍历一遍原文本，耗时 $O(N)$ ；Manacher 算法中右边界 $R$ 单调向右移动，暴力比较拓展的次数与右边界增长次数成正比，总耗时为 $O(M)$ （其中 $M \leqslant N$ ）。因此算法总体时间复杂度为严格的 $O(N)$ 。
空间复杂度： $O(N)$ 。保存原始字符及其下标映射占用 $O(N)$ 空间，构造的辅助串及回文半径数组长度为 $2M + 3$ ，总体空间消耗远低于内存限制。

总结

处理带有“过滤特定字符/忽略大小写”要求的回文串问题时，通用的有效套路是位置映射法：将有效字符提取出形成纯净子序列，并维护每个字符在原串中的下标索引。在纯净序列上运行 Manacher 算法在线性时间内定位出最优回文区间后，再通过映射下标直接在原文本中完成切片截取，既保持了算法的高效性，又完美保留了原文本中的格式与非字符信息。