codeforces-go 算法模板库：LeetCode 5 最长回文子串题解（中心扩展法 + Manacher 算法）

• 科学计算

导读

本文以 LeetCode 5. 最长回文子串（Longest Palindromic Substring） 题解为主体，系统讲解两类经典解法：中心扩展法（O(n²)）与Manacher（马拉车）算法（O(n)），并给出 Python / Java / C++ / Go 四语言的完整可运行代码。作为算法竞赛模板库 codeforces-go 的核心用例，本文还结合仓库中 copypasta/strings.go 的 Manacher 模板及 CF1326D2 等实战题目，从原理到工程实现展开纵深剖析。读完本文，你将掌握「从暴力到最优」的回文子串问题解法链，并能直接复用仓库内的 Manacher 模板解决一整套回文相关题单。

一、问题定义与朴素思路

LeetCode 5 要求：给定字符串s，返回其中最长的回文子串。

最暴力的做法是枚举所有子串，再逐个判断是否为回文串。由于共有 O(n²) 个子串，每个子串判断回文需要 O(n)，总时间复杂度高达O(n³)，无法通过较大数据规模。因此核心矛盾在于：如何更快地判断「一个子串是否为回文」。

二、方法一：中心扩展法（O(n²)）

2.1 核心思想：从中心向外扩展

观察回文串的结构特征：

• 子串abcba：最左、最右字母都是a，只要中间的bcb是回文，就能 O(1) 判定abcba是回文；
• 子串bcb：最左、最右字母都是b，只要中间的c是回文，就能 O(1) 判定bcb是回文；
• 显然c是回文。

这给出一个递推思路：与其从外向内判断，不如直接从回文中心开始向外扩展。以c为中心：

1. c本身是回文串；
2. 检查c两侧字符是否相同（都是b），于是bcb是回文；
3. 继续向外扩展（两侧都是a），于是abcba是回文。

这样每一个向外扩展步骤都能 O(1) 判定一个新子串是否回文。

2.2 奇回文串与偶回文串

• 上述abcba、bcb这类中心是单个字符的回文串，长度均为奇数，称为奇回文串；
• 形如abccba的回文串，中心在两个相邻字符之间（中间的cc），长度为偶数，称为偶回文串。从cc出发：cc是回文 → 两侧都是b，bccb是回文 → 两侧都是a，abccba是回文。

因此需要分别枚举两类中心：

• 奇回文串：枚举中心i = 0,1,...,n-1，初始化l = r = i；
• 偶回文串：枚举中心间隙i，初始化l = i，r = i + 1。

统一扩展流程：

1. 初始化l = r = i（或l = i, r = i+1）；
2. 只要s[l] == s[r]且下标不越界，就把l减一、r加一，继续判断更长的子串；
3. 循环结束时，最后一轮成功的子串是s[l+1]到s[r-1]（即左闭右开区间[l+1, r)）；
4. 若其长度r-l-1大于当前答案长度，则更新答案端点为l+1与r（左闭右开），方便最后直接切片输出具体子串。

2.3 写法一：奇偶分开判断

以下四语言代码完全等价，均维护左闭右开的答案区间[ansLeft, ansRight)：

class Solution: def longestPalindrome(self, s: str) -> str: n = len(s) ans_left = ans_right = 0 # 奇回文串 for i in range(n): l = r = i while l >= 0 and r < n and s[l] == s[r]: l -= 1 r += 1 # 循环结束后，s[l+1] 到 s[r-1] 是回文串 if r - l - 1 > ans_right - ans_left: ans_left, ans_right = l + 1, r # 左闭右开区间 # 偶回文串 for i in range(n - 1): l, r = i, i + 1 while l >= 0 and r < n and s[l] == s[r]: l -= 1 r += 1 if r - l - 1 > ans_right - ans_left: ans_left, ans_right = l + 1, r # 左闭右开区间 return s[ans_left: ans_right]

class Solution { public String longestPalindrome(String S) { char[] s = S.toCharArray(); int n = s.length; int ansLeft = 0; int ansRight = 0; // 奇回文串 for (int i = 0; i < n; i++) { int l = i; int r = i; while (l >= 0 && r < n && s[l] == s[r]) { l--; r++; } // 循环结束后，s[l+1] 到 s[r-1] 是回文串 if (r - l - 1 > ansRight - ansLeft) { ansLeft = l + 1; ansRight = r; // 左闭右开区间 } } // 偶回文串 for (int i = 0; i < n - 1; i++) { int l = i; int r = i + 1; while (l >= 0 && r < n && s[l] == s[r]) { l--; r++; } if (r - l - 1 > ansRight - ansLeft) { ansLeft = l + 1; ansRight = r; // 左闭右开区间 } } return S.substring(ansLeft, ansRight); } }

class Solution { public: string longestPalindrome(string s) { int n = s.size(); int ans_left = 0, ans_right = 0; // 奇回文串 for (int i = 0; i < n; i++) { int l = i, r = i; while (l >= 0 && r < n && s[l] == s[r]) { l--; r++; } // 循环结束后，s[l+1] 到 s[r-1] 是回文串 if (r - l - 1 > ans_right - ans_left) { ans_left = l + 1; ans_right = r; // 左闭右开区间 } } // 偶回文串 for (int i = 0; i < n - 1; i++) { int l = i, r = i + 1; while (l >= 0 && r < n && s[l] == s[r]) { l--; r++; } if (r - l - 1 > ans_right - ans_left) { ans_left = l + 1; ans_right = r; // 左闭右开区间 } } return s.substr(ans_left, ans_right - ans_left); } };

func longestPalindrome(s string) string { n := len(s) ansLeft, ansRight := 0, 0 // 奇回文串 for i := range n { l, r := i, i for l >= 0 && r < n && s[l] == s[r] { l-- r++ } if r-l-1 > ansRight-ansLeft { ansLeft = l + 1 ansRight = r // 左闭右开区间 } } // 偶回文串 for i := range n - 1 { l, r := i, i+1 for l >= 0 && r < n && s[l] == s[r] { l-- r++ } if r-l-1 > ansRight-ansLeft { ansLeft = l + 1 ansRight = r // 左闭右开区间 } } return s[ansLeft:ansRight] }

2.4 写法二：奇偶合二为一

两轮循环可以合并为一轮：枚举i = 0,1,...,2n-2，按下标奇偶性切换中心规则：

• i 为偶数：按奇回文串规则，初始化l = r = i/2（例如i = 2时l = r = 1）；
• i 为奇数：按偶回文串规则，初始化l = ⌊i/2⌋，r = ⌈i/2⌉（例如i = 1时l = 0, r = 1）。

两种情况可统一写成：l = ⌊i/2⌋，r = ⌊(i+1)/2⌋ = ⌈i/2⌉。按此规则恰好枚举到所有奇回文串中心与偶回文串中心。

func longestPalindrome(s string) string { n := len(s) ansLeft, ansRight := 0, 0 for i := range 2*n - 1 { l, r := i/2, (i+1)/2 for l >= 0 && r < n && s[l] == s[r] { l-- r++ } // 循环结束后，s[l+1] 到 s[r-1] 是回文串 if r-l-1 > ansRight-ansLeft { ansLeft = l + 1 ansRight = r // 左闭右开区间 } } return s[ansLeft:ansRight] }

Python、Java、C++ 版本与 2.3 节结构完全一致，仅将两个循环替换为for i in range(2*n-1)（C++/Java 为i < 2*n-1）并统一l, r初始化，这里不再重复列出（可对照 leetcode/problems/5.md 中的完整四语言实现）。

复杂度分析：时间复杂度 O(n²)（每个中心至多向外扩展 O(n) 次，共 2n 个中心），空间复杂度 O(1)。

仓库佐证：中心扩展法的工程化封装见 copypasta/strings.go 第 1389 行的palindromeExpandAroundCenter，与 LeetCode 官方题解入口注释并列，属于库中回文工具链的第一档（暴力/基础档）。

三、方法二：Manacher（马拉车）算法（O(n)）

3.1 为什么需要 Manacher

中心扩展法每个中心独立扩展，存在大量重复比较（例如aaaa这样的串，多个中心的扩展区间高度重叠）。Manacher 算法利用已求出的回文信息，把每个中心的计算量摊平到 O(1)，将整体复杂度优化到O(n)。

3.2 改造原串：统一为奇回文串

Manacher 的第一步是把s改造为t，在每两个字符之间以及首尾插入分隔符，并加上首尾哨兵：

• 首哨兵^（防止下标越界）；
• 每字符间及末尾插入#；
• 尾哨兵$。

例如s = "abc"→t = "^#a#b#c#$"。改造后，t中每个回文子串都有唯一的回文中心，都是奇回文串，从而不再需要区分len(s)的奇偶性。

下标转换关系（si为s中下标，ti为t中下标）：

• (si+1)*2 = ti，即ti/2-1 = si；
• ti为偶数（2, 4, 6, ...）时，对应s中的奇回文串（从 2 开始）；
• ti为奇数（3, 5, 7, ...）时，对应s中的偶回文串（从 3 开始）。

3.3 核心变量：halfLen、boxM、boxR

• 回文半径：定义奇回文串的回文半径 = (长度+1)/2，即保留回文中心、去掉一侧后的剩余长度。
• halfLen[i]：以t[i]为回文中心的最长回文子串的回文半径，即闭区间[i-halfLen[i]+1, i+halfLen[i]-1]是t上的一个回文子串。
• boxM/boxR：当前右边界下标最大的回文子串的中心位置与其右边界下标+1，关系恒为boxR = boxM + halfLen[boxM]。

3.4 算法流程（以 Go 模板为例）

func longestPalindrome(s string) string { // Manacher 模板 n := len(s) t := append(make([]byte, 0, n*2+3), '^') for _, c := range s { t = append(t, '#', byte(c)) } t = append(t, '#', '$') halfLen := make([]int, len(t)-2) halfLen[1] = 1 boxM, boxR, maxI := 0, 0, 0 for i := 2; i < len(halfLen); i++ { hl := 1 if i < boxR { // 记 i 关于 boxM 的对称位置 i'=boxM*2-i // 若以 i' 为中心的最长回文子串范围超出 boxM 回文串的范围， // 则 halfLen[i] 先初始化为已知回文半径 boxR-i，再继续暴力匹配 // 否则 halfLen[i] 与 halfLen[i'] 相等 hl = min(boxR-i, halfLen[boxM*2-i]) } // 暴力扩展 // 每次扩展后 boxR 必然右移，扩展总次数就是 boxR 右移次数，故总复杂度 O(len(t)) = O(n) for t[i-hl] == t[i+hl] { hl++ boxM, boxR = i, i+hl } halfLen[i] = hl if hl > halfLen[maxI] { maxI = i } } hl := halfLen[maxI] // t 上最长回文子串的最左、最右都是 '#' // 结合下标转换关系，得到其在 s 上的下标范围为 [(maxI-hl)/2, (maxI+hl)/2-2] return s[(maxI-hl)/2 : (maxI+hl)/2-1] }

关键点逐一拆解：

1. 对称位置复用（核心优化）：当i < boxR时，i关于boxM的对称位置是i' = boxM*2 - i。由于boxM回文串的对称性，halfLen[i]至少可以初始化为min(boxR-i, halfLen[i'])：
   • 若以i'为中心的最长回文子串完全落在boxM回文串内部，则halfLen[i] = halfLen[i']（直接复用，无需扩展）；
   • 若其超出boxM回文串范围，则先取boxR-i作为已知半径，再在此基础上继续暴力扩展。
2. 摊还分析保证 O(n)：while暴力扩展每成功一次，boxR必然右移；由于boxR单调递增、全程至多右移 O(len(t)) 次，因此所有中心的扩展次数总和为 O(n)。
3. 求最长回文子串本身：本题要求输出具体子串，因此在扫描过程中维护halfLen最大的下标maxI。由于t上回文子串的首尾一定是#（下标转换关系见代码注释），s上对应区间为[(maxI-hl)/2, (maxI+hl)/2-2]，Go 切片写作s[(maxI-hl)/2 : (maxI+hl)/2-1]。

Python、Java、C++ 版本逻辑完全一致，仅语法差异（如 Java 用Arrays.fill(t, '#')+ 手工填充构造t，C++ 用s.substr((max_i-hl)/2, hl-1)取子串），完整代码见 leetcode/problems/5.md。

复杂度分析：时间复杂度 O(n)，空间复杂度 O(n)（需存储t与halfLen数组）。

四、仓库实战：Manacher 模板在 codeforces-go 中的工程化应用

4.1 模板库中的 Manacher 全家桶

codeforces-go 在 copypasta/strings.go 第 672–954 行内置了完整的回文工具链（该文件同时收录了 OI Wiki、cp-algorithms 等参考链接，以及洛谷 P3805、Yosupo 判题等模板题链接）：

• manacher（strings.go）：完整版模板，除求halfLen外，还附带了以下可直接复用的衍生能力：
  • O(1) 区间回文判定isPal(l, r)：halfLen[l+r+2] > r-l+1，用于 CF1326D2、CF7D、CF835D 等题；
  • 以s[i]（或s[i],s[i+1]）为中心的最长奇/偶回文长度midLen(i, odd)；
  • 最长回文子串长度 + 所有最长回文子串起点；
  • 回文子串总数（∑ halfLen[i]/2，对应 LeetCode 647 回文子串）；
  • 以s[i]为首/尾字母的最长回文长度（对应洛谷 P4555 最长双回文串、LeetCode 214 最短回文串、LC1960）；
  • 基于差分数组的「以 i 结尾/开头回文子串个数」预处理（对应 CF159D、CF17E）。
• manacherOdd（strings.go）：不插入#、不加哨兵的奇回文专用版，对应 LC1960、CF30E；
• manacherEven（strings.go）：偶回文专用版，对应 CF1827C。

4.2 实战题：CF1326D2（去掉子串后剩余部分是回文串）

main/1300-1399/1326D2.go 是该模板的典型应用：先去掉s两侧相同的字符得到中间剩余段，再对剩余段跑 Manacher，利用回文判定函数q(l,r) = maxLen[l+r+2]-1 >= r-l+1找出可去掉的最长回文前缀或后缀，最终输出「前缀回文 + 剩余 + 后缀回文」的最短拼接结果。

manacher := func(origin string) { n := len(origin) s := make([]byte, 2*n+3) s[0] = '^' for i := range origin { s[2*i+1] = '#' s[2*i+2] = origin[i] } s[2*n+1] = '#' s[2*n+2] = '$' maxLen = make([]int, 2*n+3) var mid, right int for i := 1; i < 2*n+2; i++ { if i < right { maxLen[i] = min(maxLen[2*mid-i], right-i) } else { maxLen[i] = 1 } for s[i+maxLen[i]] == s[i-maxLen[i]] { maxLen[i]++ } if right < i+maxLen[i] { mid = i right = i + maxLen[i] } } } q := func(l, r int) bool { return maxLen[l+r+2]-1 >= r-l+1 }

4.3 实战题：LeetCode 周赛 319D / 420D

• leetcode/weekly/319/d/d.go：题目要求选出不重叠、长度至少为k的回文子串的最大数目。代码先用 Manacher 建出halfLen，再用isPalindrome(l,r) = halfLen[l+r+1] > r-l做 O(1) 回文判定，最后配合贪心/DP 求解，展示了「Manacher 预处理 + 业务逻辑」的拆分范式。
• leetcode/weekly/420/d/d.go：将树的 DFS 后序遍历串作为待判定字符串，对每个节点子树的[begin, end)区间用isPalindrome(l,r) = halfLen[l+r+1] > r-l判断是否回文，是 Manacher 与树上区间问题的结合。

上述用例共同印证：Manacher 模板的价值远不止求最长回文子串，其halfLen数组是「任意区间是否回文」的 O(1) 判定表，可直接嵌入各类计数、DP、贪心与树/图问题。

五、专题训练与延伸

围绕本题的 Manacher 部分，仓库模板注释（copypasta/strings.go）整理了覆盖 1800–3500 分段的题单，可逐题巩固：

• 模板题：洛谷 P3805、Yosupoenumerate_palindromes；
• 入门到进阶：CF1326D2（1800）、CF7D（2200）、CF835D（1900）、CF1080E（2400）、AtCoder ABC398F；
• 综合应用：CF1827C（2600，回文分拆）、CF30E（2800）、CF159D、CF17E（2900，相交回文对）、CF1081H（3500）、洛谷 P4555、LC1745（三回文分割）、LC2472（不重叠回文子串）、LC647（回文子串计数）、LC1960（两回文乘积）、LC214（最短回文串）、LC3327（DFS 字符串回文判定，即周赛 420D）。

题单分类（滑动窗口、字符串 KMP/Z 函数/Manacher 等）可参见题解末尾的 leetcode/problems/5.md 分类链接；仓库内更多解法与测试可继续浏览 leetcode/problems 目录与 leetcode/weekly 系列。

六、总结

从 O(n³) 暴力到 O(n²) 中心扩展，再到 O(n) Manacher，本文完整覆盖了 LeetCode 5 的最优解法链；结合 codeforces-go 模板库中的manacher/manacherOdd/manacherEven与 CF1326D2、周赛 319D/420D 等实战用例，读者可以一键迁移这套回文模板，直接应对题单中从入门到 3500 分段的所有回文类问题。

• 科学计算