回文子串这个问题我最早是在刷题时撞上的。当时用最朴素的中心扩展法写完还挺得意结果一提交数据量一上来直接超时卡在最后几个大用例上。后来翻题解才知道有个叫 Manacher 的算法能把时间复杂度压到线性第一次看那堆下标变换和半径数组说实话是懵的。这篇就把我踩过的坑、绕过的弯、以及最后真正理解它的那个瞬间完整地摊开讲一遍。Manacher 算法圈内常叫马拉车解决的核心问题就一个给定一个字符串在 O(n) 时间内求出它的最长回文子串。它适合所有正在啃字符串算法、被中心扩展的 O(n²) 卡住、想搞懂线性解法到底“线性”在哪里的朋友。哪怕你之前完全没接触过回文相关算法只要会写基本的 C 循环和数组跟着往下走也能吃透。下面我会从设计思路、核心原理、C 实现、边界处理到常见坑一层层拆开。1. 为什么需要 Manacher从暴力到线性的思路演进1.1 先看清暴力解法的瓶颈在哪求最长回文子串最直觉的做法是枚举所有子串再判断每个子串是不是回文。枚举子串本身是 O(n²)每次判断又要 O(n)总复杂度 O(n³)字符串长度上千就基本没法看了。稍微聪明一点的是中心扩展法枚举每一个可能的回文中心然后向两边同时扩展直到字符不相等为止。这个思路把判断和枚举合并了复杂度降到 O(n²)。中心扩展的关键洞察是回文串一定有一个“中心”。奇数长度的回文中心是一个字符偶数长度的回文中心是两个字符之间的空隙。所以中心一共有 2n-1 个n 个字符中心加 n-1 个空隙中心。对每个中心向外扩最坏情况下每个中心都要扩到边界比如字符串全是同一个字符aaaa...a每个中心都能扩到两端总工作量就是 O(n²)。我当初就是栽在这个“全相同字符”的用例上。表面上看平均情况很快但算法复杂度看的是最坏情况出题人只要给一串相同字符中心扩展立刻现原形。这就是必须上 Manacher 的直接原因——它要做的就是把“每个中心重复扩展”这件事里的大量冗余计算砍掉。1.2 Manacher 的核心思想复用已经算过的信息Manacher 的聪明之处和 KMP 利用已匹配前缀信息是同一个哲学不重复计算已经确定的东西。中心扩展时我们从左到右依次处理每个中心当处理到靠右的中心时左边很多中心的回文半径其实已经算出来了。如果当前中心落在某个已知回文串的内部那么它关于那个回文串中心的对称点信息是可以直接拿来用的。打个生活化的比方你在一条街上从左往右量每个路灯到某栋标志建筑的距离量到后面发现某段路是对称的那么右边某个路灯到标志建筑的距离其实和它左边镜像位置那个路灯的距离是一样的根本不用重新走一遍。Manacher 干的就是这件事用一个不断向右推进的“最右回文边界”作为参照把每个中心能扩的起点直接跳到对称点告诉我们的位置从而避免从头扩展。这个“复用”带来的效果是虽然每个中心看起来还在向外扩但整体上右边界只增不减最多推进到 n所以总扩展次数是线性的。这就是 O(n) 的来源也是理解整个算法的钥匙。很多人背下了代码却说不清为什么是 O(n)症结就在于没抓住“右边界单调右移”这个不变量。1.3 奇偶长度统一处理插入分隔符的巧思中心扩展还有个烦人的地方奇数长度和偶数长度要分开处理代码里到处是两套逻辑容易写错。Manacher 用了一个非常漂亮的技巧——在字符之间以及首尾插入统一的分隔符把任意字符串都变成奇数长度。具体做法是在原串每个字符左右都插一个特殊符号比如用#同时在首尾也加上这样长度变成 2n1必然是奇数。比如aba变成#a#b#a#abba变成#a#b#b#a#。这样一来原来偶数长度的回文abba在新串里对应的是以中间#为中心的回文所有回文都统一成“以某个字符为中心”的奇数长度形式一套逻辑通吃。这里有个细节值得说清楚分隔符必须是一个在原串中绝对不会出现的字符。如果原串只含小写字母用#没问题但如果原串可能包含任意 ASCII 字符就得选一个确定不冲突的符号或者干脆用整数数组重新编码。我见过有人图省事直接用原串里可能出现的字符当分隔符结果在某些用例上答案莫名其妙偏大排查半天才发现是分隔符和真实字符撞了导致虚假回文。这个坑后面还会细说。2. 核心原理拆解半径数组与对称复用2.1 半径数组 p[i] 到底记录了什么Manacher 维护一个数组pp[i]表示以处理后的字符串第 i 个位置为中心能向外扩展的回文半径。注意这里的“半径”定义要统一我习惯的定义是包含中心在内的回文长度的一半向下取整再加一也就是从中心到回文最右端含的字符个数。比如#a#b#a#中以b下标 3为中心回文是#a#b#a#从中心到右端是#a#共 3 个字符所以p[3] 3。这个定义下p[i] - 1恰好就是原串中以该中心对应的最长回文子串长度。为什么因为处理后的串里回文半径每多一个字符对应到原串就多一个真实字符分隔符不算所以p[i] - 1就是原串回文长度。这个换算关系是整个算法输出答案的关键一定要记牢。我一开始用的是另一种半径定义不含中心结果换算公式对不上答案总是差一折腾了好久才统一。2.2 最右回文边界与中心两个必须维护的变量除了半径数组算法还要维护两个变量center当前已知回文中能延伸到最右的那个回文的中心和right这个回文能到达的最右位置即center p[center] - 1。这两个变量是“复用信息”的载体。处理每个新位置 i 时先判断 i 是否落在[center, right]这个区间内。如果i right说明 i 在已知最右回文的内部那么它关于 center 的对称点mirror 2 * center - i的回文信息可以部分复用。具体能复用多少取决于对称点的回文是否超出了当前回文的左边界如果p[mirror] right - i 1说明对称点的回文完全被当前回文包住那么p[i]至少等于p[mirror]可以直接赋值不用扩展。如果p[mirror] right - i 1说明对称点的回文超出了当前回文范围那么p[i]至少等于right - i 1即 i 到右边界的距离超出的部分需要继续向外扩展验证。如果i right说明 i 在已知回文之外没有任何信息可复用p[i]从 1 开始老老实实向外扩。这段逻辑是 Manacher 的心脏也是最容易写错的地方。我建议初学时把mirror的推导在纸上画一遍center 在中间i 在右边mirror 在左边三者满足i mirror 2 * center所以mirror 2 * center - i。画过一次就再也不会记错了。2.3 为什么整体复杂度是 O(n)右边界单调性很多人会疑惑代码里明明有while循环在向外扩展怎么保证不是 O(n²)关键在于right这个变量只增不减。每次 while 循环成功扩展一次right就会向右推进至少一格。而right最大只能到处理后字符串的长度 2n1所以整个算法过程中while 循环体内成功执行的次数总和不超过 2n1。那些“失败”的扩展即比较一次发现字符不等就退出呢每个位置 i 最多触发一次失败的比较总共 n 个位置所以失败比较也是 O(n)。成功扩展 O(n) 加上失败比较 O(n)总复杂度就是 O(n)。这个论证是理解 Manacher 线性的核心比死记“它是 O(n)”有意义得多。我当时就是把这个“势能分析”想通了才真正敢在比赛里放心用。3. C 实现从预处理到答案提取的完整代码3.1 预处理构造带分隔符的新串先看预处理。假设原串是s长度 n。我们构造一个新串t长度2n 1规则是t[0] #然后对每个原字符依次放入s[i]和#。这样t的下标 0、2、4... 是分隔符1、3、5... 是原字符。string preprocess(const string s) { string t #; for (char c : s) { t c; t #; } return t; }这段代码简单但有个隐含前提分隔符#不能和原串字符冲突。如果原串可能包含#就得换一个。更稳妥的做法是用一个原串里绝对没有的字符或者干脆用整数编码。我在实际项目里处理可能含任意可见字符的输入时会先扫描一遍原串选一个没出现过的 ASCII 字符作为分隔符虽然多一次 O(n) 扫描但换来的是绝对安全。提示分隔符冲突是隐蔽性极强的 bug。它不会让程序崩溃只会让某些用例的答案偏大因为分隔符和真实字符相等时会产生本不存在的“回文”。调试时如果发现答案比预期大优先怀疑分隔符。3.2 主循环半径计算与边界更新主循环是算法的核心我把它拆成清晰的几段来写方便对照理解string longestPalindrome(string s) { if (s.empty()) return ; string t preprocess(s); int m t.size(); vectorint p(m, 0); int center 0, right 0; int maxLen 0, maxCenter 0; for (int i 0; i m; i) { // 步骤一利用对称性确定初始半径 if (i right) { int mirror 2 * center - i; p[i] min(right - i 1, p[mirror]); } else { p[i] 1; } // 步骤二尝试向外扩展 while (i - p[i] 0 i p[i] m t[i - p[i]] t[i p[i]]) { p[i]; } // 步骤三更新最右边界 if (i p[i] - 1 right) { center i; right i p[i] - 1; } // 步骤四记录全局最优 if (p[i] maxLen) { maxLen p[i]; maxCenter i; } } // 提取答案 int start (maxCenter - maxLen 1) / 2; return s.substr(start, maxLen - 1); }逐段解释一下。步骤一的min(right - i 1, p[mirror])就是前面讲的复用逻辑的代码化能复用的上限是“对称点半径”和“i 到右边界距离”两者的较小值。这里用right - i 1而不是right - i是因为半径定义包含了中心边界处理要一致差一错误往往就出在这里。步骤二的 while 循环负责扩展注意边界检查i - p[i] 0 i p[i] m必须放在字符比较之前否则会越界。C 里有短路特性所以这样写是安全的。步骤三更新边界条件是i p[i] - 1 right即新的回文右端超过了旧的 right 才更新。这个“严格大于”保证了 right 单调右移是复杂度分析的依据。步骤四记录最优用p[i] maxLen而不是这样在长度相同时保留最先出现的那个结果稳定。3.3 答案提取从处理后下标还原到原串答案提取是最容易出错的一步因为涉及两套坐标系的换算。maxCenter是处理后串的中心下标maxLen是处理后的半径。原串中回文的起始位置是(maxCenter - maxLen 1) / 2长度是maxLen - 1。这个公式怎么来的处理后串的回文左端是maxCenter - maxLen 1这个下标对应到原串因为每两个处理后的字符对应一个原字符所以除以 2 向下取整就是原串起点。长度方面处理后半径maxLen里包含了分隔符真实字符数是maxLen - 1。我建议你拿aba和abba两个例子手动代入验证一遍把maxCenter、maxLen、start都算出来验证一次就彻底记住了。注意整数除法在 C 里是向下取整对于非负下标没问题。但如果你的实现里下标可能为负一般不会要小心。另外maxLen - 1当maxLen为 1 时结果是 0对应空串虽然实际不会出现至少有一个字符但边界上心里要有数。4. 实操验证与常见问题排查4.1 用典型用例做手动走查光看代码不够我习惯拿几个典型串手动走一遍确认每一步的p值符合预期。下面这张表是我当初验证时记录的以abba为例处理后是#a#b#b#a#下标 i字符 t[i]对称点 mirror初始 p[i]扩展后 p[i]centerright0#-11001a-12122#013243b122244#015485b322486#233487a122488#01148最终maxLen 5maxCenter 4start (4 - 5 1) / 2 0长度5 - 1 4得到abba正确。这张表建议你自己也画一遍尤其是下标 3 和 5 这两个位置它们展示了“对称点半径被边界截断”的情况是理解复用逻辑的关键样本。4.2 常见问题速查表实际写和调的过程中我整理了一份高频问题清单基本都是新手包括当年的我会踩的问题现象可能原因排查与解决答案比预期大分隔符与原串字符冲突换一个原串中不存在的分隔符答案比预期小 1半径定义与长度换算不一致统一用“含中心”定义长度取 p[i]-1程序越界崩溃while 边界检查顺序写反先检查下标范围再比较字符某些用例超时误用了 O(n²) 的中心扩展确认复用了 mirror 信息right 单调偶数长度回文丢失预处理漏了首尾分隔符确保新串长度是 2n1结果不稳定更新最优用了 改用 保留首次出现这张表里前两个是我亲身踩过的。尤其是“答案比预期大”那个当时排查了很久最后发现是测试数据里恰好含有我选的分隔符导致虚假回文。从那以后我养成了习惯分隔符要么用确定不冲突的要么先扫描确认。4.3 几个容易被忽略的实操心得第一个心得是关于半径定义的统一。网上不同博客对p[i]的定义五花八门有的含中心有的不含有的从 0 开始有的从 1 开始。你抄代码时如果混用了两种定义答案一定错。我的建议是选定一种定义后把“初始值、扩展条件、边界更新、答案换算”四处全部按这个定义对齐写完后用aba和abba各验证一次确认无误再往下走。第二个心得是关于空串和单字符的边界。空串直接返回空单字符返回它自己这两个特判虽然简单但漏了会在某些平台上触发越界。我在longestPalindrome开头加了if (s.empty()) return ;单字符其实会被主逻辑正确处理处理后是#a#半径 2长度 1所以不用额外特判但心里要清楚它能过。第三个心得是性能验证。Manacher 是 O(n)但常数不小预处理、数组分配、多次比较。如果你在极端性能场景下用它可以预先reserve新串的容量避免反复扩容或者用静态数组代替vector。我实测过对百万级长度的串reserve能省下可观的时间虽然不影响复杂度但工程上值得做。5. 算法边界与延伸思考5.1 Manacher 适合什么、不适合什么Manacher 专治“单个字符串的最长回文子串”在这个问题上它是最优的线性解法没有之一。但它不是万能的如果你要统计所有回文子串的个数或者求每个位置为中心的回文数量Manacher 的半径数组其实已经包含了这些信息p[i]就反映了以 i 为中心的回文个数可以直接复用。但如果你要处理的是“最长回文子序列”不要求连续那是另一个问题得用区间 DPManacher 帮不上忙。还有一个容易混淆的点Manacher 求的是“最长”如果你需要“所有本质不同的回文子串”那要用回文自动机Eertree复杂度也是 O(n)但数据结构和 Manacher 完全不同。选型时先明确需求是“最长”还是“全部”别拿错工具。5.2 和其他回文算法的对比为了让你对 Manacher 的定位更清晰我列个简单对比算法解决的问题时间复杂度空间复杂度适用场景中心扩展最长回文子串O(n²)O(1)短串、快速实现Manacher最长回文子串O(n)O(n)长串、性能敏感区间 DP最长回文子序列O(n²)O(n²)子序列问题回文自动机本质不同回文子串O(n)O(n)统计类问题从表里能看出Manacher 的定位很明确连续子串、求最长、要线性。它的空间开销是 O(n) 的半径数组加预处理串对内存敏感的场景要注意但一般竞赛和工程场景都能接受。5.3 一个值得动手的扩展练习如果你想真正吃透我建议做这个练习改造 Manacher让它不仅返回最长回文子串还返回所有长度大于等于 2 的回文子串的起始位置和长度。提示在记录最优的那一步不要只记全局最大而是遍历p数组对每个p[i] 1的位置用同样的换算公式还原出原串中的回文。这个练习能逼你把坐标换算彻底搞明白做完之后你对 Manacher 的理解会上一个台阶。我自己做完这个练习后最大的收获是意识到Manacher 的半径数组其实是一个信息密度极高的结构它把“以每个中心的最长回文”都存下来了最长回文只是从中取了个最大值而已。理解了这一点你就能根据需求灵活地从p数组里挖出想要的信息而不是死记一个模板。最后分享一个我调试时的小技巧写个暴力中心扩展的版本作为对照随机生成大量小字符串两个版本对拍。Manacher 的 bug 往往只在特定对称结构下暴露随机对拍能快速定位。我当初就是靠对拍发现了分隔符冲突那个隐蔽 bug比盯着代码看效率高多了。
到O(n)的最长回文子串优化)
