别再暴力匹配了！用Manacher算法在Python/Go里高效处理回文问题（附竞赛模板）-平芜编程栈

高效回文处理实战：Manacher算法在Python/Go中的竞赛级实现

回文串处理是算法竞赛和工程开发中的经典问题。当面对力扣周赛的"统计所有回文子串"或是Codeforces中需要高效求解最长双回文串的题目时，传统中心扩展法O(n²)的时间复杂度往往成为性能瓶颈。本文将深入解析Manacher算法的核心思想，并提供可直接套用的Python/Go竞赛模板。

1. 回文问题与暴力解法局限

回文串指正读反读相同的字符串，如"abba"或"abcba"。常见处理场景包括：

统计字符串中所有回文子串数量
寻找最长回文子串
构造特殊回文结构
双回文串拼接问题

传统中心扩展法的实现简单直接：

def count_palindromes(s: str) -> int: n = len(s) count = 0 def expand(l, r): nonlocal count while l >= 0 and r < n and s[l] == s[r]: count += 1 l -= 1 r += 1 for i in range(n): expand(i, i) # 奇数长度 expand(i, i+1) # 偶数长度 return count

这种方法需要处理奇偶两种情况，且时间复杂度为O(n²)，当n>10⁴时（如洛谷P3805），必然超时。

2. Manacher算法核心原理

Manacher算法通过巧妙的预处理和动态维护，将时间复杂度降至O(n)。其核心创新点包括：

2.1 统一奇偶处理

通过插入特殊字符（如'#'）消除奇偶差异：

原始字符串："abba" → 处理为："#a#b#b#a#"

这使得任意回文中心都落在字符上，无需区分奇偶情况。

2.2 关键变量维护

算法维护三个核心变量：

r数组：记录每个位置的最大回文半径
中心C：当前向右延伸最远的回文中心
最右边界R：C对应的回文串右边界

维护过程遵循以下规则：

当i在R内时，利用对称性初始化r[i]
继续中心扩展更新r[i]
若i的右边界超过R，则更新C和R

这种动态维护避免了重复计算，是算法高效的关键。

3. Python竞赛模板实现

def manacher(s: str) -> int: # 预处理字符串 t = ['#'] for c in s: t.append(c) t.append('#') t = ''.join(t) n = len(t) r = [0] * n C = R = max_len = 0 for i in range(1, n-1): # 利用对称性初始化半径 mirror = 2 * C - i if i < R: r[i] = min(r[mirror], R - i) # 中心扩展 while (i - 1 - r[i] >= 0 and i + 1 + r[i] < n and t[i - 1 - r[i]] == t[i + 1 + r[i]]): r[i] += 1 # 更新最右边界 if i + r[i] > R: C, R = i, i + r[i] max_len = max(max_len, r[i]) return max_len # 洛谷P3805模板题解法 s = input().strip() print(manacher(s))

该模板可直接用于求解最长回文子串问题，时间复杂度严格O(n)。

4. Go语言高性能实现

对于内存敏感或需要极致性能的场景，Go实现能更好利用底层内存：

package main import ( "fmt" "strings" ) func manacher(s string) int { t := "#" + strings.Join(strings.Split(s, ""), "#") + "#" n := len(t) r := make([]int, n) C, R, maxLen := 0, 0, 0 for i := 1; i < n-1; i++ { mirror := 2*C - i if i < R { r[i] = min(r[mirror], R-i) } for i-1-r[i] >= 0 && i+1+r[i] < n && t[i-1-r[i]] == t[i+1+r[i]] { r[i]++ } if i+r[i] > R { C, R = i, i+r[i] } if r[i] > maxLen { maxLen = r[i] } } return maxLen } func min(a, b int) int { if a < b { return a } return b } func main() { var s string fmt.Scan(&s) fmt.Println(manacher(s)) }

Go版本通过预分配slice和减少字符串操作，性能比Python提升3-5倍，适合处理超长字符串（如n>10⁶）。

5. 进阶应用：最长双回文串问题

洛谷P4555要求找到不相交的两个回文子串，其长度之和最大。Manacher算法经过扩展可高效解决：

def longest_double_palindrome(s: str) -> int: t = ['#'] for c in s: t.append(c) t.append('#') t = ''.join(t) n = len(t) r = [0] * n C = R = 0 left = [0] * n # 记录左侧最长回文 right = [0] * n # 记录右侧最长回文 for i in range(1, n-1): mirror = 2 * C - i if i < R: r[i] = min(r[mirror], R - i) while (i - 1 - r[i] >= 0 and i + 1 + r[i] < n and t[i - 1 - r[i]] == t[i + 1 + r[i]]): r[i] += 1 if i + r[i] > R: C, R = i, i + r[i] # 更新左右边界信息 left[i + r[i]] = max(left[i + r[i]], r[i]) right[i - r[i]] = max(right[i - r[i]], r[i]) # 处理边界传播 for i in range(2, n, 2): right[i] = max(right[i], right[i-2] - 2) for i in range(n-3, 0, -2): left[i] = max(left[i], left[i+2] - 2) max_len = 0 for i in range(2, n-1, 2): if left[i] > 0 and right[i] > 0: max_len = max(max_len, left[i] + right[i]) return max_len

该解法通过维护左右边界数组，在O(n)时间内完成双回文串的查找，相比暴力O(n³)有质的飞跃。

6. 算法变体与优化技巧

在实际应用中，Manacher算法可根据场景进行多种优化：

6.1 内存优化版

当仅需最长回文长度时，可只维护当前最右边界而非整个r数组：

func compactManacher(s string) int { t := "#" + strings.Join(strings.Split(s, ""), "#") + "#" n := len(t) C, R, maxLen := 0, 0, 0 for i := 1; i < n-1; i++ { var r int if i < R { r = min(2*C-i, R-i) } for i-1-r >= 0 && i+1+r < n && t[i-1-r] == t[i+1+r] { r++ } if i+r > R { C, R = i, i+r } if r > maxLen { maxLen = r } } return maxLen }