时间限制: 1.00s 内存限制: 125.00MB
题目描述
据说如果你给无限只母牛和无限台巨型便携式电脑（有非常大的键盘 ), 那么母牛们会制造出世上最棒的回文。你的工作就是去寻找这些牛制造的奇观（最棒的回文）。
在寻找回文时不用理睬那些标点符号、空格（但应该保留下来以便做为答案输出）, 只用考虑字母 A∼Z 和 a∼z。要你寻找的最长的回文的文章是一个不超过 20,000 个字符的字符串。我们将保证最长的回文不会超过 2,000 个字符（在除去标点符号、空格之前）。
输入格式
输入文件不会超过 20,000 字符。这个文件可能一行或多行，但是每行都不超过 80 个字符（不包括最后的换行符）。
输出格式
输出的第一行应该包括找到的最长的回文的长度。
下一行或几行应该包括这个回文的原文（没有除去标点符号、空格），把这个回文输出到一行或多行（如果回文中包括换行符）。
如果有多个回文长度都等于最大值，输出最前面出现的那一个。
输入 #1
Confucius say: Madam, I'm Adam.输出 #1
11 Madam, I'm Adam说明/提示
题目翻译来自NOCOW。
USACO Training Section 1.3
一、题目理解
1.1 问题描述
在一个混合了字母、标点、空格、换行符的字符串（最长 20000 字符）中，找出最长的回文子串，要求：
判断回文时忽略非字母字符（只考虑 A-Z a-z）
字母不区分大小写（'a' 和 'A' 视为相同）
输出时要保留原字符串中的全部字符（包括标点、空格、换行）
如果有多个最长回文，输出最先出现的那个
保证最长回文在去掉非字母前不超过 2000 字符
1.2 输入输出示例：
输入： Confucius say: Madam, I'm Adam. 输出： 11 Madam, I'm Adam解释：忽略标点空格后，字母序列是"ConfuciussayMadamImAdam"，但最长回文是"MadamImAdam"的部分？不对，实际上"Madam, I'm Adam"去掉标点空格后是"MadamImAdam"，这就是最长的回文。
"Madam, I'm Adam"去掉非字母 →"MadamImAdam"正着：
M a d a m I m A d a m反着：
m a d A m I m a d a M统一小写后正反都是
"madamimadam"，确实是一个回文，长度 11
1.3 关键约束
原串长度 ≤ 20000
去掉非字母后的最长回文长度 ≤ 2000
时间限制 1 秒
这意味着我们不能在 O(n²) 时间复杂度下对原串的每个子串都检查一遍。
二、解题思路
2.1 核心难点
非字母干扰：回文判断时，标点和空格需要被忽略
输出完整性：找到的回文在输出时必须包含原串中的标点、空格、换行
大小写不敏感：判断时忽略大小写
效率要求：O(n²) 可能超时，需要 O(n) 或 O(n log n) 算法
2.2 算法选择
方案一：中心扩展法（O(n²) 理论上不可行）
对每个中心向两边扩展，需要跳过非字母。最坏情况 O(n²) ≈ 4×10⁸，可能超时。但考虑到最长回文长度 ≤ 2000，实际扩展次数有限，可能勉强通过。
方案二：Manacher 算法（O(n) 推荐）
在过滤后的字母序列上使用 Manacher 算法，复杂度 O(n)，完全可行。
2.3 整体思路
读入原串（保留换行符）
过滤出字母，记录每个字母在原串中的索引
在过滤后的字母序列上使用 Manacher 算法找最长回文
根据找到的中心和半径，确定回文在过滤序列中的起止位置
通过记录的索引，在原串中截取对应的子串输出
三、Manacher 算法详解
3.1 算法原理
Manacher 算法可以在 O(n) 时间内找出字符串的最长回文子串。它利用回文的对称性，避免重复计算。
核心数组
d1[i]：以 i 为中心的奇回文半径（半径定义为从中心到一端的长度，包含中心）回文长度 = 2×d1[i] - 1
例如：
"abcba"，中心 i=2('c')，d1[2]=3，长度=5
d2[i]：以 i 右侧间隙为中心的偶回文半径回文长度 = 2×d2[i]
例如：
"abba"，间隙在 i=1('b')右侧，d2[1]=2，长度=4
维护变量
l, r：当前已知的最右回文的左右边界利用对称性：当 i 在 [l, r] 内时，可以借用对称点 j = l + r - i 的 d1[j] 值
3.2 算法步骤（奇回文）
初始化 l = 0, r = -1 for i = 0 to n-1: k = 1 if i > r else min(d1[l+r-i], r-i+1) while i-k >= 0 and i+k < n and t[i-k] == t[i+k]: k++ d1[i] = k k-- if i+k > r: l = i-k r = i+k3.3 示例演示
以"madamimadam"为例（长度 11）：
索引: 0 1 2 3 4 5 6 7 8 9 10 字符: m a d a m i m a d a m 计算 d1[5] (中心在 'i'): - i=5, 初始 k=1 - 比较位置4('m')和6('m')，相等，k=2 - 比较3('a')和7('a')，相等，k=3 - 比较2('d')和8('d')，相等，k=4 - 比较1('a')和9('a')，相等，k=5 - 比较0('m')和10('m')，相等，k=6 - 越界，停止 d1[5] = 6，回文长度 = 2×6-1 = 11四、详细实现步骤
4.1 读取输入：
string s; char ch; while (cin.get(ch)) { // 逐字符读取，包括换行符 s += ch; }4.2 过滤字母：
vector<pair<char, int>> filtered; // (小写字母, 原串下标) for (int i = 0; i < s.size(); i++) { if (isalpha(s[i])) { filtered.push_back({tolower(s[i]), i}); } }4.3 Manacher 算法实现：
int n = filtered.size(); vector<char> t(n); for (int i = 0; i < n; i++) t[i] = filtered[i].first; // 奇回文 vector<int> d1(n); int l = 0, r = -1; for (int i = 0; i < n; i++) { int k = (i > r) ? 1 : min(d1[l + r - i], r - i + 1); while (i - k >= 0 && i + k < n && t[i - k] == t[i + k]) k++; d1[i] = k--; if (i + k > r) { l = i - k; r = i + k; } } // 偶回文 vector<int> d2(n); l = 0, r = -1; for (int i = 0; i < n; i++) { int k = (i > r) ? 0 : min(d2[l + r - i + 1], r - i + 1); while (i - k - 1 >= 0 && i + k < n && t[i - k - 1] == t[i + k]) k++; d2[i] = k--; if (i + k > r) { l = i - k - 1; r = i + k; } }4.4 寻找最优解：
int max_len = 0; int best_start = 0, best_end = 0; // 在 filtered 中的索引 // 检查奇回文 for (int i = 0; i < n; i++) { int len = 2 * d1[i] - 1; if (len > max_len) { max_len = len; best_start = i - (d1[i] - 1); best_end = i + (d1[i] - 1); } } // 检查偶回文 for (int i = 0; i < n; i++) { int len = 2 * d2[i]; if (len > max_len) { max_len = len; best_start = i - d2[i]; best_end = i + d2[i] - 1; } }4.5 映射回原串并输出：
int orig_start = filtered[best_start].second; int orig_end = filtered[best_end].second; cout << max_len << endl; cout << s.substr(orig_start, orig_end - orig_start + 1);五、边界情况处理
5.1 无字母的情况：
if (n == 0) { cout << 0 << endl << endl; return 0; }5.2 单个字符的情况
Manacher 算法能正确处理：d1[i] = 1，回文长度为 1。
5.3 多个最长回文
取最先出现的：因为遍历是从左到右，当len > max_len时才更新，相等时不更新，自然保留了最早出现的。
5.4 跨行回文
由于我们保留换行符，整个字符串被打平处理，跨行的回文也能被正确找到。
六、复杂度分析
时间复杂度：O(n)，n ≤ 20000，Manacher 算法每个位置最多扩展有限次
空间复杂度：O(n)，存储原串、filtered 数组和 Manacher 数组
七、完整代码：
#include <iostream> #include <string> #include <vector> #include <cctype> #include <algorithm> using namespace std; int main() { // 读取整个输入 string s; char ch; while (cin.get(ch)) { s += ch; } // 过滤字母 vector<pair<char, int>> filtered; for (int i = 0; i < (int)s.size(); i++) { if (isalpha(s[i])) { filtered.push_back({tolower(s[i]), i}); } } int n = filtered.size(); if (n == 0) { cout << 0 << endl << endl; return 0; } // 提取字母数组 vector<char> t(n); for (int i = 0; i < n; i++) { t[i] = filtered[i].first; } // Manacher 奇回文 vector<int> d1(n); int l = 0, r = -1; for (int i = 0; i < n; i++) { int k = (i > r) ? 1 : min(d1[l + r - i], r - i + 1); while (i - k >= 0 && i + k < n && t[i - k] == t[i + k]) { k++; } d1[i] = k; k--; if (i + k > r) { l = i - k; r = i + k; } } // Manacher 偶回文 vector<int> d2(n); l = 0, r = -1; for (int i = 0; i < n; i++) { int k = (i > r) ? 0 : min(d2[l + r - i + 1], r - i + 1); while (i - k - 1 >= 0 && i + k < n && t[i - k - 1] == t[i + k]) { k++; } d2[i] = k; k--; if (i + k > r) { l = i - k - 1; r = i + k; } } // 找最长回文 int max_len = 0; int best_start_f = 0, best_end_f = 0; for (int i = 0; i < n; i++) { int len = 2 * d1[i] - 1; if (len > max_len) { max_len = len; best_start_f = i - (d1[i] - 1); best_end_f = i + (d1[i] - 1); } } for (int i = 0; i < n; i++) { int len = 2 * d2[i]; if (len > max_len) { max_len = len; best_start_f = i - d2[i]; best_end_f = i + d2[i] - 1; } } // 映射回原串 int orig_start = filtered[best_start_f].second; int orig_end = filtered[best_end_f].second; // 输出 cout << max_len << endl; cout << s.substr(orig_start, orig_end - orig_start + 1); return 0; }八、测试用例
测试1：基本示例：
输入：Confucius say: Madam, I'm Adam. 输出： 11 Madam, I'm Adam测试2：全大写：
输入：ABBA 输出： 4 ABBA测试3：包含标点：
输入：A man, a plan, a canal, panama! 输出： 21 A man, a plan, a canal, panama测试4：跨行:
输入：hello world abba good 输出： 4 abba测试5：无字母:
输入：123 !@# 输出： 0九、常见问题与注意事项
为什么不能用原串直接跑 Manacher？
因为标点和空格影响判断，需要在比较时跳过，这会破坏 Manacher 的对称性前提
为什么要记录原串索引？
因为输出时需要保留标点、空格、换行，不能直接用过滤后的字符串输出
为什么用
cin.get()而不是getline？getline会去掉换行符，但题目要求输出包含换行符，所以需要保留
大小写处理
判断时统一转小写，但输出原文保留原样
多个最长回文取最先出现
代码中通过
len > max_len而不是len >= max_len实现
十、总结
本题的核心是：
过滤降维：将问题从混合字符空间降维到纯字母空间
高效算法：使用 Manacher 算法在 O(n) 时间内找到最长回文
还原输出：通过索引映射保留原始格式
这种"预处理 + 高效算法 + 后处理映射"的思路是解决此类字符串问题的经典模式。
