当前位置：首页 > news >正文

从‘马拉车’到‘回文中心’：图解Manacher算法，让晦涩概念一目了然

news 2026/4/25 8:25:21

从‘马拉车’到‘回文中心’：图解Manacher算法，让晦涩概念一目了然

第一次接触回文串问题时，大多数人会本能地想到中心扩展法——从每个字符向两侧扫描，直到发现不对称的字符为止。这种方法简单直接，但当处理长字符串时，其O(n²)的时间复杂度往往让人望而却步。1975年，计算机科学家Glenn Manacher提出了一种巧妙的线性时间算法，通过利用回文串的对称性质，将时间复杂度降至O(n)。这个算法后来被亲切地称为"马拉车算法"，不仅因为其英文名谐音，更因为它像一辆高效的马车，能快速遍历字符串的每个角落。

1. 理解回文串的核心挑战

回文串的对称美在数学上令人着迷，但在计算机处理时却带来了两个棘手问题：

奇偶性困境：长度为5的"ababa"（奇数长度）和长度为4的"abba"（偶数长度）具有不同的对称中心结构
重复计算：传统中心扩展法对每个字符独立扩展，无法利用已发现的回文串信息

1.1 预处理：统一奇偶情况

Manacher算法的第一个精妙之处在于预处理：

def preprocess(s: str) -> str: return '#' + '#'.join(s) + '#' print(preprocess("abba")) # 输出：#a#b#b#a#

这种插入特殊字符（通常用#）的方法实现了两个关键效果：

将原始字符串长度从n扩展到2n+1，确保总是奇数长度
新字符串中每个原始字符两侧都有#，统一了处理逻辑

转换效果对比：

原始字符串	转换后	最长回文半径
"aba"	"#a#b#a#"	[0,1,0,3,0,1,0]
"abba"	"#a#b#b#a#"	[0,1,0,1,4,1,0,1,0]

2. 算法核心：利用对称性避免重复计算

2.1 关键概念解析

回文中心(C)：当前已知右边界最远的回文串中心位置
半径数组(r[])：记录每个位置能扩展的最大回文半径
最右边界(R)：C + r[C]，即当前已知回文串能达到的最右索引

提示：半径r[i]表示以i为中心的回文串向左右能扩展的字符数，不包括中心本身

2.2 对称点优化原理

当扫描到位置i时，如果i在当前最右回文串范围内（i < R），则可以找到其关于中心C的对称点i'：

情况一：i'的回文完全在C的回文内 → r[i] = r[i']
情况二：i'的回文超出C的左边界 → r[i] = R - i
情况三：i'的回文刚好到达左边界 → 从R开始继续扩展

def manacher(s: str) -> list: T = preprocess(s) n = len(T) r = [0] * n C = R = 0 for i in range(1, n-1): mirror = 2 * C - i # 计算i关于C的对称点 if i < R: r[i] = min(R - i, r[mirror]) # 尝试扩展 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] return r

3. 可视化执行流程

以字符串"abababa"为例，观察算法执行过程：

步骤	当前中心C	最右R	处理i	操作
1	0	0	1	暴力扩展，r[1]=1
2	1	2	2	对称点i'=0，r[2]=0
3	1	2	3	对称点i'=-1，暴力扩展，r[3]=3
4	3	6	4	对称点i'=2，r[4]=min(6-4,0)=0
5	3	6	5	对称点i'=1，r[5]=min(6-5,1)=1
6	5	7	6	对称点i'=4，r[6]=min(7-6,0)=0