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]的含义
预处理之后，我们需要维护一个数组p，p[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 = 4，p - 1 = 3，对应原字符串s = "aba"的长度，正好是3。另一个例子，t = "#a#b#b#a#"，中间“#”的p = 5，p - 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(); vector<int> 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中的下标是3，maxLen = 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 变形一：求字符串内回文子串的总个数
马拉车算法不只是能求“最长的回文子串”，它还能顺手解决“一共有多少个回文子串”这一类问题。回顾数组p，p[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对你来说就不再是背模板，而是真正握住了一把解决回文串问题的钥匙。后续遇到任何和回文相关的题目，你都会自然想到它。
