Manacher/马拉车算法最长回文子串问题可以说是字符串算法里的一道“家常菜”。我入行这几年面试遇到过它竞赛里见过它连实际做文本处理的工单系统都曾经撞上过它。很多朋友学这个算法时容易卡住总觉得代码不长、边界条件却绕得人头疼。这篇博文我就把马拉车算法Manacher从原理到代码再到底层逻辑完整拆开尽量用大白话讲清楚它到底牛在哪。先给没接触过的朋友一句话讲明白马拉车算法是求解“一个字符串里的最长回文子串”的线性时间复杂度算法复杂度是O(n)。它解决的核心问题就是——给你一个字符串快速找出最长的、左右对称的那一段。比如“babad”里最长回文子串是“bab”或“aba”“cbbd”里是“bb”。暴力法能做但遇见长字符串会超时Manacher出现后就彻底把这题变简单了。这篇文章适合正在刷题、准备面试或者纯粹想提升字符串处理功底的开发者来读。1. 从暴力到中心扩展为什么要折腾出马拉车1.1 暴力解法和它的致命弱点先说最直白的解法。给你一个字符串s想知道哪一段是回文最没脑子的做法是枚举所有子串的起点和终点然后逐个字符去验证这一段是不是回文。这个时间复杂度是多少呢枚举起点和终点本身是O(n²)再验证每个子串是否是回文又要O(n)合起来O(n³)。字符串稍微长一点比如一万个字符那基本就等死机了。一个稍微聪明点的办法是“中心扩展法”。回文串天然有个特性它有一个对称中心从中心往左右两边扩展时两边的字符永远相等。枚举每一个位置作为中心然后左右同时扩直到不能扩为止记录下最长的长度。这个方法时间复杂度降到了O(n²)代码也好写。但问题依然存在一旦字符串长度到达几万甚至几十万级别O(n²)依旧扛不住。1.2 中心扩展法在细节上有什么麻烦中心扩展法还有一个特别容易被忽视的坑回文串的长度可能是奇数也可能是偶数。奇数的回文串中心是一个字符比如“aba”的中心是“b”偶数的回文串中心是在两个字符之间比如“abba”的中心是“bb”之间的那条缝。所以中心扩展法必须把“单个字符”和“字符间隙”都当成中心来枚举也就是有2n-1个中心。这一步处理不好代码会出现各种漏解或者越界。你可能会想为什么不直接在每个字符之间塞入一个特殊字符把偶数长度变成奇数长度呢恭喜你这个思路正是马拉车算法的第一步。它通过这种“变奇数”的处理让所有情况统一起来减少分类讨论的负担。这个思路很简单但有谁能想到它能配合一个“回文半径数组”把整体复杂度压到O(n)呢这就是Manacher的巧妙所在。1.3 马拉车到底改进了什么马拉车算法干的活儿归纳成一句话就是利用已知回文串的对称性减少重复匹配把中心扩展法的O(n²)变成O(n)。它不再傻傻地让每个中心都从零开始扩展而是借助之前已经算好的信息“跳跃式”地给新的中心一个初始半径再继续往外扩。这个思想其实生活中到处都有。比如你在读一本推理小说已经知道第五章的某个段落是对称结构等看到第六章疑似有同样结构时你没必要从第一个字重新比对直接从第五章得出的对称信息往后接着看就行。马拉车算法做的就是这件事尽可能站在前人的肩膀上不做无意义的重复劳动。2. 算法核心思路预处理、半径数组和最关键的对称性2.1 字符串改造把奇数偶数统一起来马拉车算法首先会对原始字符串做一次预处理。假设原字符串是s我们构造一个新字符串t。做法是在每个字符两边插入一个不会出现的分隔符比如“#”然后在开头和结尾也各加一个“#”。比如s abba处理后变成t #a#b#b#a#。为什么这么做呢因为原来偶数长度回文串“abba”的中心在“bb”之间的缝隙上如果用“#”把这个缝隙撑开那“#a#b#b#a#”的回文中心就变成了中间的那个“#”它是个实打实的字符位置。这样一来新字符串里所有回文子串都是奇数长度中心永远是一个确定的字符位置实现起来不用再额外处理偶数情况。这个预处理是后面所有公式成立的基础。2.2 回文半径数组p[i]的含义预处理之后我们需要维护一个数组pp[i]表示以t[i]为中心的最长回文子串的“半径长度”注意这里的半径是包含中心字符本身的。更准确点说如果以t[i]为中心能扩展出回文串那么从中心到边界的长度记为p[i]。比如t #a#b#a#以中间的“b”为中心回文串是“#a#b#a#”半径p 4因为从中心的“b”到最右端一共4个字符。这里有一个非常实用的映射关系原字符串s中某个回文子串的长度恰好等于预处理后t中对应的p[i] - 1。这个结论几乎是所有题解里直接拿来用的但很多人没用懂。我们拿例子验一下t #a#b#a#中间“b”的p 4p - 1 3对应原字符串s aba的长度正好是3。另一个例子t #a#b#b#a#中间“#”的p 5p - 1 4对应原串“abba”的长度正好是4。这个性质非常关键因为我们最终要的就是最长原始回文子串的长度。2.3 最核心的复用逻辑对称性如何省时间现在到了整个算法的灵魂部分。我们维护两个变量id是当前已经找到的、能覆盖到最右边界的所有回文串中那个“最右边界”对应的回文中心mx是id所对应的回文串的右边界位置。也就是说目前已知的最靠右的回文串是t[id - p[id]] 到 t[id p[id]]这段mx id p[id]。当我们扫描到新的位置i时如果i在mx的左边说明i落在已知回文串的范围之内。那么以i为中心至少能有多大的回文半径呢利用对称性找到i关于id的对称点 j 2 * id - i。因为整个id区间是回文串所以j位置的回文情况可以“映射”给i。不过这里有个限制如果j的回文范围超出了id串的左边界那么i的回文范围也不能超过mx。所以i的初始半径可以安全地取 min(p[j], mx - i)。如果i在mx的右边没法偷懒初始半径只能设为1。这个“能复用就复用不能复用才重新扩展”的策略就是马拉车从O(n²)变成O(n)的秘密所在。每个字符最多被扩展失败一次所以总体每个字符只会被访问常数次。很多教程直接甩这个公式但没讲明白为什么取min我建议你亲手画一下t数组的图把i、j、id、mx标出来推导一遍就会发现这个取min是“安全”和“高效”之间的精确平衡点。3. 完整实现与核心代码解析3.1 基础版C代码下面给出一个完整且好理解的Manacher实现我习惯直接用vector存储处理后的字符串和半径数组清晰不易错。#include iostream #include string #include vector #include algorithm using namespace std; string manacher(const string s) { // 1. 预处理构造带分隔符的新串 string t #; for (char c : s) { t c; t #; } int n t.size(); vectorint p(n, 0); int id 0, mx 0; // id当前最右回文串的中心mx该回文串的右边界 int maxLen 0, centerIndex 0; // 2. 主循环 for (int i 0; i n; i) { // 核心复用步骤如果i在mx之内用对称点初始化p[i] if (i mx) { int j 2 * id - i; p[i] min(p[j], mx - i); } else { p[i] 1; } // 3. 中心扩展 while (i - p[i] 0 i p[i] n t[i - p[i]] t[i p[i]]) { p[i]; } // 4. 更新id和mx if (i p[i] mx) { mx i p[i]; id i; } // 5. 记录全局最大 if (p[i] maxLen) { maxLen p[i]; centerIndex i; } } // 6. 根据中心位置和半径还原原始子串 int start (centerIndex - maxLen 1) / 2; return s.substr(start, maxLen - 1); } int main() { string s babad; cout manacher(s) endl; // 输出 bab 或 aba return 0; }3.2 为什么p[i]初始化要看mx - i很多初学朋友都会在min(p[j], mx - i)这一行卡住。我来拆开解释。当i mx时i处于id的回文区间中那么i关于id的对称点j也一定在区间中。因为整个大区间是回文t[j]两边的情况会镜像地出现在t[i]两边。所以j的回文半径p[j]理论上可以直接“复制”给i。但有一种例外j的回文区域可能超出id区间的左边界一旦超出就代表镜像到右边时也会超出mx而mx之后的情况我们还没验证过不能直接假设它仍然对称。因此i的初始半径不能超过mx - i因为在mx之外的那部分信息是未知的。取两者的较小值既利用了已知信息又不越界假设安全且高效。3.3 还原原始回文子串的公式推导预处理字符串t的长度和原字符串s的长度有对应关系。t中每个原始字符的下标是偶数0, 2, 4...每个井号的下标是奇数。假设以t[centerIndex]为中心的最长回文串半径是maxLen那么该回文串在原字符串中的起始下标就是(centerIndex - maxLen 1) / 2长度就是maxLen - 1。这个公式有除法整数向下取整之所以成立是因为原串中字符位置与预处理串中位置的映射关系是1比2。我建议你不必死记这个公式直接构造一个简单例子走一遍。比如s aba映射到t #a#b#a#中心“b”在t中的下标是3maxLen 4。(3 - 4 1) / 2 0正好对应原串下标0。长度maxLen - 1 3。如果是偶数串s abba映射到t #a#b#b#a#中心是下标5的那个“#”maxLen 5(5 - 5 1) / 2 0长度4都对得上。4. 实战中的变体应用从最长回文子串到各类衍生问题4.1 变形一求字符串内回文子串的总个数马拉车算法不只是能求“最长的回文子串”它还能顺手解决“一共有多少个回文子串”这一类问题。回顾数组pp[i]表示以t[i]为中心的最大半径那么以t[i]为中心的、所有可能存在的回文子串一共有p[i] - 1个去掉半径1代表单个字符本身注意单个字符也算回文子串所以实际上p[i]个。更准确地说p[i]的值代表“以当前中心能扩展出来的回文串数量”累加p[i]就是预处理串里所有回文中心贡献的数然后通过除法换算回原字符串的计数。我第一次用这个思路解决LeetCode 647时代码改动量很小就是把求maxLen改为累加。但要注意因为预处理串加入了“#”每一个中心在原串中可能代表字符中心或字符间隙中心累加时要自动区分不过Manacher的优势恰好是无需区分统一计算就行。4.2 变形二动态规划结合Manacher优化区间DP有些区间DP问题中需要快速判断任意子串是否为回文。传统做法是用二维布尔数组预处理复杂度O(n²)。如果用Manacher我们可以先算出每个中心的回文半径再把“某个区间是否回文”的判定变成O(1)。这在做“分割回文串最少切割次数”这类题目时非常有用。比如LeetCode 132“分割回文串 II”如果用纯区间DP加中心扩展总复杂度O(n³)会超时。但先跑一遍Manacher拿到p数组之后DP状态转移时快速查询子串是否回文整体复杂度能降到O(n²)。这种组合技巧在实际竞赛中特别常见值得专门练一练。4.3 变形三双串拼接与字符串哈希还有一类场景是多字符串处理比如判断把一个字符串A插入另一个字符串B的某个位置后能否形成最长回文串。这类问题通常的做法是把A和B拼接起来中间加一个特殊字符然后跑Manacher。特殊字符的作用是防止回文跨越两个字符串的边界因为正常情况下跨边界的回文并不是题目要求的结果。这个技巧和字符串哈希配合使用时能解决很多看起来非常绕的字符串构造题。我记得有一次处理一个文本编辑器项目需要高亮显示一段文本中所有的回文片段。直接暴力中心扩展在长文本上经常掉性能后来我把这段文本按行切分对每行跑一次Manacher再在全文本级别做一次合并效果非常稳定。虽然这是一个很小的优化点但让我切实体会到O(n)算法在生产环境中的价值。5. 运行时性能分析与实测对比5.1 时间复杂度直观理解很多教程直接说“Manacher是O(n)”但理由往往一笔带过。我用自己的理解讲一下为什么它严格是O(n)。虽然代码里有一个while循环用来扩展半径表面上看起来像O(n²)但关键在于mx一直在单调向右推进。每一次成功扩展都会让mx增大而mx只有n个位置可走所以总扩展次数不超过n次。再加上每个i只被处理一遍所以主循环的均摊复杂度就是O(n)。理解了这个再去看while里的比较操作就不会觉得它“暴破”了。5.2 和中心扩展法的实际差距我本地用随机生成的十万级字符串做过对比测试。当字符串长度在1000以内时中心扩展法和Manacher差距不明显都能秒出结果。但长度到达50000时中心扩展法耗时可能已经是秒级甚至更高而Manacher依然保持在毫秒级别。这个差距在竞赛评测和面试手撕代码时会直接决定题目能不能过。优化点再补充一个预处理字符串时可以用reserve提前分配内存减少vector扩容带来的损耗。虽然对整体复杂度没影响但在极大数据规模下这种零碎性能优化能省几十毫秒。5.3 空间复杂度和优化空间Manacher的空间复杂度是O(n)主要是半径数组p。有些极致的做法是直接在原字符串上操作不建新串但那样代码可读性极差我不推荐。工程开发优先读代码体验刷题追求清晰度和正确率别为了省一点空间把自己绕晕。如果你的场景内存非常受限可以考虑用short或int数组替代vector但大部分情况下没必要。6. 常见问题与排查技巧实录6.1 边界越界问题预处理后别忘了保护条件写Manacher最容易犯的错就是while循环里的越界。在代码中一定要确保i - p[i] 0 i p[i] n否则访问t的负下标或者越界下标会直接导致运行时错误。我见过很多新手在本地测试小字符串时碰巧没越界一上评测就崩原因就在这里。建议在写while之前就把边界条件写好不要依赖数据恰好不会越界。6.2 字符串含特殊字符导致结果错误预处理时如果原始字符串本身就包含“#”那结果会乱套。实际开发中原始字符串可能来自用户输入什么样的字符都可能出现。稳妥起见在构造t之前可以先判断一下s中是否含有分隔符如果有换一个ASCII码中不常见的字符比如\001或者在哈希时直接用唯一的分隔符做映射我一般用|或^核心原则是保证它不会出现在原串中。6.3 还原原始子串时偏移量算错还原子串的start和length公式是另一个容易翻车的地方。如果你发现返回的子串和预期对不上多半是这里出了问题。我自己的排查方法是打印centerIndex、maxLen和t字符串手工算一遍映射关系马上就能定位。这个公式变形比较多遇到不确定时可以在代码里写注释并附带一个小样例验证。6.4 刷题时不同平台的语言差异C的vector下标是size_t类型和负数比较时会警告甚至出错。如果你在while里写i - p[i] 0注意类型转换问题。建议先将索引转为int类型。Java和Python则不太有这个问题但Python的性能在超大字符串上确实不如C如果你用Python刷字符串题Manacher虽然优化了复杂度本身常数还是偏大可以选择PyPy或者尽量用下标遍历代替切片。7. 马拉车算法的变体和拓展思路7.1 长度扩展不只是简单回文还有“最长双回文串”有一类更进阶的问题比如“最长双回文串”要求从某个位置把字符串切成两段每一段都能各自构成回文串然后求这两段回文总长度最大。这个问题可以先用Manacher算出每个位置左侧的最长回文半径和右侧的最长回文半径再一次遍历切分点求解。本质上就是Manacher配合前后缀预处理的典型用法。7.2 结合二分答案处理“回文判定”类问题在一些交互题中系统只允许有限次查询某个子串是否回文这时可以借助Manacher预处理之后的半径数组把每次查询变成O(1)。这样可以低成本应对大量查询也不需要建二维DP表。尤其是在一轮需要多次二分答案的题目中这种优化能把总复杂度压到很理想的范围。7.3 其他语言移植注意点如果你用Java实现建议使用char[]数组代替String的charAt能减少一些时间开销。Python实现需要注意列表下标访问相对较慢可以把t转换为list后再操作。Go语言里切片操作十分顺手但要注意字符串是不可变类型频繁拼接会产生大量内存复制。工程里多语言踩坑之后我总结的经验是算法核心思路不变但每个语言在实现细节上都值得做点微调。最后分享一点实际操作中的经验我个人做了大量字符串题之后最大的体会是Manacher不仅仅是一个“会做就能过”的模板算法它更重要的价值在于训练一种“利用已知信息避免重复计算”的思维模式。这和动态规划有异曲同工之妙只不过Manacher把这种复用建立在回文串天然的对称性上。初学的时候不要在代码层面死磕先用小样例在纸上把id、mx、p数组的每一步变化都写出来。我当初学这个算法时手动模拟了三四个例子才真正理解了min(p[j], mx - i)那一行是怎么来的。一旦想通这个Manacher对你来说就不再是背模板而是真正握住了一把解决回文串问题的钥匙。后续遇到任何和回文相关的题目你都会自然想到它。