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

从‘马拉车’到‘回文中心’图解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扩展到2n1确保总是奇数长度新字符串中每个原始字符两侧都有#统一了处理逻辑转换效果对比原始字符串转换后最长回文半径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 r3. 可视化执行流程以字符串abababa为例观察算法执行过程步骤当前中心C最右R处理i操作1001暴力扩展r[1]12122对称点i0r[2]03123对称点i-1暴力扩展r[3]34364对称点i2r[4]min(6-4,0)05365对称点i1r[5]min(6-5,1)16576对称点i4r[6]min(7-6,0)0关键观察点当i3时通过暴力扩展发现长回文将R推到6i4和i6都直接利用了对称信息避免重复计算i5虽然利用了对称信息但仍需少量扩展4. 复杂度分析与实际应用4.1 为什么是O(n)算法性能依赖于两个关键观察R单调递增每次扩展都使R严格增大对称点优化大部分情况直接确定r[i]无需扩展注意while循环的总次数不超过n次因为R最多增长到n4.2 典型应用场景最长回文子串直接取max(r)即为解双回文串问题预处理左右最大回文信息回文计数统计所有可能回文组合性能对比方法时间复杂度空间复杂度适用场景暴力法O(n²)O(1)短字符串动态规划O(n²)O(n²)需要所有子串信息ManacherO(n)O(n)单次查询最长回文在实际编码竞赛中Manacher算法因其高效性成为解决回文问题的首选。例如处理长度为10⁶的字符串时暴力方法可能需要数秒而Manacher能在毫秒级完成。