洛谷 P1210 [USACO1.3] 最长的回文 Calf Flac（内有完整思路）[Manacher 算法][字符串]

时间限制: 1.00s 内存限制: 125.00MB题目描述据说如果你给无限只母牛和无限台巨型便携式电脑有非常大的键盘 ), 那么母牛们会制造出世上最棒的回文。你的工作就是去寻找这些牛制造的奇观最棒的回文。在寻找回文时不用理睬那些标点符号、空格但应该保留下来以便做为答案输出, 只用考虑字母 A∼Z 和 a∼z。要你寻找的最长的回文的文章是一个不超过 20,000 个字符的字符串。我们将保证最长的回文不会超过 2,000 个字符在除去标点符号、空格之前。输入格式输入文件不会超过 20,000 字符。这个文件可能一行或多行但是每行都不超过 80 个字符不包括最后的换行符。输出格式输出的第一行应该包括找到的最长的回文的长度。下一行或几行应该包括这个回文的原文没有除去标点符号、空格把这个回文输出到一行或多行如果回文中包括换行符。如果有多个回文长度都等于最大值输出最前面出现的那一个。输入 #1Confucius say: Madam, Im Adam.输出 #111 Madam, Im Adam说明/提示题目翻译来自NOCOW。USACO Training Section 1.3一、题目理解1.1 问题描述在一个混合了字母、标点、空格、换行符的字符串最长 20000 字符中找出最长的回文子串要求判断回文时忽略非字母字符只考虑 A-Z a-z字母不区分大小写a 和 A 视为相同输出时要保留原字符串中的全部字符包括标点、空格、换行如果有多个最长回文输出最先出现的那个保证最长回文在去掉非字母前不超过 2000 字符1.2 输入输出示例输入 Confucius say: Madam, Im Adam. 输出 11 Madam, Im Adam解释忽略标点空格后字母序列是ConfuciussayMadamImAdam但最长回文是MadamImAdam的部分不对实际上Madam, Im Adam去掉标点空格后是MadamImAdam这就是最长的回文。Madam, Im 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确实是一个回文长度 111.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中心 i2(c)d1[2]3长度5d2[i]以 i 右侧间隙为中心的偶回文半径回文长度 2×d2[i]例如abba间隙在 i1(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[lr-i], r-i1) while i-k 0 and ik n and t[i-k] t[ik]: k d1[i] k k-- if ik r: l i-k r ik3.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): - i5, 初始 k1 - 比较位置4(m)和6(m)相等k2 - 比较3(a)和7(a)相等k3 - 比较2(d)和8(d)相等k4 - 比较1(a)和9(a)相等k5 - 比较0(m)和10(m)相等k6 - 越界停止 d1[5] 6回文长度 2×6-1 11四、详细实现步骤4.1 读取输入string s; char ch; while (cin.get(ch)) { // 逐字符读取包括换行符 s ch; }4.2 过滤字母vectorpairchar, 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(); vectorchar t(n); for (int i 0; i n; i) t[i] filtered[i].first; // 奇回文 vectorint 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; } } // 偶回文 vectorint 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 ≤ 20000Manacher 算法每个位置最多扩展有限次空间复杂度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; } // 过滤字母 vectorpairchar, 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; } // 提取字母数组 vectorchar t(n); for (int i 0; i n; i) { t[i] filtered[i].first; } // Manacher 奇回文 vectorint 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 偶回文 vectorint 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, Im Adam. 输出 11 Madam, Im 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()而不是getlinegetline会去掉换行符但题目要求输出包含换行符所以需要保留大小写处理判断时统一转小写但输出原文保留原样多个最长回文取最先出现代码中通过len max_len而不是len max_len实现十、总结本题的核心是过滤降维将问题从混合字符空间降维到纯字母空间高效算法使用 Manacher 算法在 O(n) 时间内找到最长回文还原输出通过索引映射保留原始格式这种预处理 高效算法 后处理映射的思路是解决此类字符串问题的经典模式。本期分享到这里谢谢大家的观看