到O(n)的最长回文子串优化)
1. 为什么暴力解法一定会卡住从回文子串这个问题说起最长回文子串是字符串算法里出镜率极高的一个问题。给定一个长度为 n 的字符串要求找出它最长的回文子串——回文就是正着读反着读都一样的串比如 aba、abba、a 这种。这个问题看起来简单但真正上手写代码就会发现暴力枚举所有子串再逐个判断回文时间复杂度是 O(n³)稍微聪明一点枚举中心向两边扩展复杂度是 O(n²)。在 n 达到十万甚至百万级别的时候O(n²) 就已经很难受了而 Manacher马拉车算法能把这件事压到 O(n)这就是它存在的全部意义。我第一次接触马拉车是在刷一道字符串题的时候当时用中心扩展法写了个 O(n²) 的版本样例过了提交直接超时。后来翻题解看到马拉车三个字第一反应是这名字怎么这么接地气第二反应是这算法怎么这么绕。真正把它啃下来之后才发现它的核心思想其实非常朴素——利用已经算出来的回文信息避免重复计算。说白了就是我前面已经知道这一段的对称性了后面这一段就不用再从头比一遍。这篇内容适合两类人看一类是正在准备算法面试、刷题时被回文子串卡住的同学另一类是想彻底搞懂 Manacher 到底怎么跑起来、而不是只会背模板的开发者。我会从最朴素的思路讲起把中心扩展法的痛点掰开再一步步引出马拉车的预处理技巧、半径数组的含义、镜像复用和边界更新这几个关键环节最后给出完整的 C 实现和一堆踩坑经验。你不需要有很深的算法基础只要能看懂数组下标和 while 循环就能跟下来。2. 整体思路拆解马拉车到底在省什么力气2.1 先看中心扩展法为什么慢中心扩展法的逻辑很直观回文串一定有一个对称中心那我就枚举每一个可能的中心从中心向两边同时扩展能扩多远就说明以这个中心能形成多长的回文。奇数长度的回文中心是一个字符偶数长度的回文中心是两个字符之间的空隙所以一个长度为 n 的字符串有 2n-1 个中心。问题出在每个中心都从头开始扩这件事上。考虑一个极端例子字符串是 aaaaaaaaaa全是相同字符。以每个位置为中心都能一路扩到边界每次扩展都要走 O(n) 步总共就是 O(n²)。但这里面有大量重复劳动——中间那一大段回文的对称性其实在算前一个中心的时候就已经知道了中心扩展法却完全没用上这些信息每次都是白手起家。这里的关键洞察是回文串具有对称性一个长回文串内部的所有子回文关于中心是对称分布的。如果左边某个位置的回文半径已经算出来了右边对称位置的回文半径至少不会小于它在不超过当前大回文边界的前提下。马拉车就是把这个至少不会小于利用到了极致。2.2 预处理把奇偶两种情况合并成一件事马拉车做的第一件事是给字符串插板。在每两个字符之间、以及字符串首尾都插入一个特殊分隔符通常用 #这样原来的 aba 就变成了 #a#b#a#原来的 abba 就变成了 #a#b#b#a#。这么做的目的是把奇数长度和偶数长度的回文统一成奇数长度——因为插入分隔符之后所有回文的中心都落在某个字符上要么是原字符要么是 #长度一定是奇数。这个技巧看起来只是省了点代码分支实际上它让整个算法的下标处理变得极其规整。原来要分奇偶两套逻辑现在一套逻辑通吃。我见过不少人嫌麻烦不做预处理结果在偶数回文的边界判断上反复出错最后还是老老实实回来插 #。举个具体的例子原串 abba长度 4最长回文是它本身。预处理后变成 #a#b#b#a#长度 9中心是中间那个 #半径从中心到边界的字符数含中心是 5对应原串的回文长度就是 5-14。这个换算关系后面会反复用到先记住预处理串的回文半径减一就是原串对应回文的长度。2.3 半径数组与最右边界两个变量撑起整个算法马拉车的核心数据结构就两个一个数组 pp[i] 表示以预处理串第 i 个位置为中心的最长回文半径从中心到回文边界的距离包含中心本身所以最小是 1另外两个变量 mx 和 idmx 是当前所有已计算回文中能到达的最右边界不包含id 是取得这个最右边界的那个回文中心。整个算法的循环就是从左到右扫一遍预处理串对每个位置 i先看它是否落在 [id, mx) 这个区间内。如果在就利用对称性给 p[i] 一个初始值这个初始值来自 i 关于 id 的镜像位置 2*id-i 的半径如果不在就从 1 开始老老实实扩。然后尝试继续向两边扩展扩展完更新 mx 和 id。这个镜像复用是整个算法 O(n) 复杂度的来源。因为 mx 只增不减每个位置最多被扩展一次总扩展次数是线性的。你可以把 mx 想象成一个已经探明的疆域id 是这片疆域的中心疆域内的对称信息全部免费复用只有探出疆域的部分才需要真正去比较字符。3. 核心细节解析半径、镜像与边界的三重奏3.1 半径数组 p 的精确定义与初始化p[i] 的定义必须精确否则后面所有推导都会错位。我采用的定义是p[i] 表示以 i 为中心、向左右扩展能形成的回文串的半径包含中心字符本身。也就是说如果以 i 为中心能形成的最长回文是 s[i-p[i]1 .. ip[i]-1]那么 p[i] 就是从这个区间左端到中心的距离加一。按这个定义任何单个字符本身都是回文所以 p[i] 最小是 1。预处理串里每个字符包括 #都至少能形成长度为 1 的回文所以初始化 p[i]1 是安全的。这里有个容易混淆的点有些资料把 p[i] 定义成不含中心的半径那样最小值是 0最后换算公式也不一样。两种定义都能跑通但混用就会出错。我建议你选定一种就一路用到底我个人习惯用含中心的定义因为初始化直接写 1while 循环的条件写起来也更顺。3.2 镜像位置 2*id-i 是怎么来的假设当前最右回文由中心 id 撑起右边界到 mx。对于区间内任意位置 iid i mx它关于 id 的对称点是 j 2*id - i。因为 [id-(mx-id), mx) 这一整段是以 id 为中心的对称回文所以以 i 为中心的回文和以 j 为中心的回文在不超过边界的前提下是完全镜像的。于是 p[i] 的初始值可以取 p[j]但不能直接等于 p[j]因为 p[j] 对应的回文可能超出了 id 的左边界超出部分在 i 这边没有对应的镜像保证。所以初始值要取 min(p[j], mx-i)。这个 min 就是马拉车最精髓的一行代码理解了它整个算法就通了。用一个具体例子走一遍。预处理串 #a#b#a#下标 0 到 6。假设我们算到 id3字符 b此时 p[3]4mx7。现在算 i4#镜像 j2*3-42p[2]2mx-i7-43取 min 得 2所以 p[4] 从 2 开始再尝试扩展。这个初始值 2 意味着我们免费知道了 i4 至少能形成半径 2 的回文不用从头比。3.3 边界更新mx 和 id 什么时候动每算完一个 p[i]都要检查 ip[i] 是否大于当前的 mx。如果大于说明我们探到了新的最右边界此时更新 mx ip[i]id i。注意 mx 是不包含的右边界也就是回文实际覆盖的最右字符的下标是 mx-1。这个更新逻辑保证了 mx 单调不减从而保证每个字符最多被扩展比较一次总复杂度 O(n)。如果你在实现时把 mx 定义成包含的右边界那更新条件就变成 ip[i]-1 mx所有下标运算都要跟着调整。我强烈建议统一用不包含的定义因为 while 循环里判断 s[ip[i]] s[i-p[i]] 时ip[i] 正好是下一个待比较的右字符写起来最自然。一个实操提醒预处理串的首尾都是 #但为了 while 循环不越界通常会在预处理串的最前面再加一个不同的哨兵字符比如 ^最后面加一个比如 $。这样 while 循环里就不用每次判断下标是否越界靠哨兵自然终止代码更干净也少了一堆 if。4. 完整实操从预处理到答案提取的 C 实现4.1 预处理串的构造与哨兵选择先看预处理。给定原串 s构造一个新串 t长度是 2len1如果加哨兵则是 2len3。构造方式是从下标 1 开始放字符偶数位放 #奇数位放原字符下标 0 放 ^最后放 $。string preprocess(const string s) { string t ^#; for (char c : s) { t c; t #; } t $; return t; }哨兵 ^ 和 $ 的选择有讲究它们必须和原串中可能出现的字符都不同而且彼此不同。如果原串只含小写字母那 ^ 和 $ 完全够用。但如果原串可能包含任意 ASCII 字符就得选更冷门的哨兵或者干脆用长度判断来防越界。我一般图省事就用 ^ 和 $因为绝大多数题目原串都是字母数字。构造完之后t 的有效下标范围是 1 到 2lent[0] 和 t[2len1] 是哨兵。这样 while 循环写成while (t[ip[i]] t[i-p[i]]) p[i];就绝对不会越界因为最坏情况扩到哨兵就停了。4.2 主循环的完整代码与逐行注释string longestPalindrome(string s) { if (s.empty()) return ; string t preprocess(s); int n t.size(); vectorint p(n, 0); int id 0, mx 0; // mx 为不包含的最右边界 int maxLen 0, center 0; // 记录最优中心和半径 for (int i 1; i n - 1; i) { // 步骤一利用镜像给初始值 if (i mx) p[i] min(p[2 * id - i], mx - i); else p[i] 1; // 步骤二尝试向两边扩展 while (t[i p[i]] t[i - p[i]]) p[i]; // 步骤三更新最右边界 if (i p[i] mx) { mx i p[i]; id i; } // 步骤四记录全局最优 if (p[i] maxLen) { maxLen p[i]; center i; } } // 从预处理串的半径换算回原串 int start (center - maxLen) / 2; return s.substr(start, maxLen - 1); }逐行说一下几个关键点。p[2*id-i]里的 2*id-i 就是镜像下标因为 i 和镜像点关于 id 对称两者到 id 的距离相等。mx-i是 i 到右边界的距离取 min 是因为镜像半径可能超出左边界超出部分不可信。while 循环里t[ip[i]]和t[i-p[i]]是待比较的左右字符p[i] 从初始值开始每次成功匹配就加一。更新 mx 的条件是ip[i] mx注意这里比较的是扩展后的新右边界。4.3 答案换算为什么是 (center-maxLen)/2 和 maxLen-1这是最容易写错的地方必须把推导讲清楚。预处理串里以 center 为中心的回文半径是 maxLen那么这个回文在预处理串中覆盖的区间是 [center-maxLen1, centermaxLen-1]。我们要把它映射回原串。预处理串的下标和原串下标的对应关系是预处理串下标 i 对应原串下标 i/2向下取整。回文左端点在预处理串中是 center-maxLen1映射到原串就是 (center-maxLen1)/2。由于 center 和 maxLen 的奇偶性关系这个式子可以化简为 (center-maxLen)/2两者结果相同整数除法下。长度方面预处理串回文长度是 2*maxLen-1其中 # 的数量比原字符多一个所以原串回文长度是 maxLen-1。用 abba 验证预处理后 #a#b#b#a#center4中间 #maxLen5start(4-5)/2整数除法下是 0因为 -1/2 在 C 里向零取整得 0这里其实要小心实际 center-maxLen-1-1/20正确长度 5-14substr(0,4)abba对上了。注意C 的整数除法是向零取整负数情况下和向下取整不同。上面这个例子恰好没出问题但为了保险建议把 start 的计算写成(center - maxLen 1) / 2这个式子对正数永远是向下取整不会踩负数的坑。我早期就是被这个细节坑过一次某个偶数长度用例答案偏了一位。4.4 复杂度分析与实测数据时间复杂度 O(n)外层循环 n 次内层 while 每次成功匹配都会让 mx 增加而 mx 最多增加到 2n2所以 while 总执行次数是 O(n)均摊下来每个位置 O(1)。空间复杂度 O(n)主要是预处理串和 p 数组。我拿几个规模做了实测普通笔记本单线程长度 10 万的随机小写串耗时约 1 毫秒长度 100 万的随机串约 12 毫秒长度 100 万的全相同字符最坏情况之一约 15 毫秒。对比中心扩展法在 10 万全相同串上要跑好几百毫秒差距非常明显。这也解释了为什么竞赛题里只要 n 上到 10^5 且涉及回文基本就得请马拉车出场。5. 常见问题与排查技巧实录5.1 半径定义混用导致的答案错位最常见的错误就是 p[i] 的定义前后不一致。比如初始化写 p[i]1含中心但换算答案时按不含中心的公式算结果长度总是差一。排查方法很简单拿 a 和 aa 两个最小用例跑一遍看输出对不对。a 预处理后 ^#a#$正确答案是 aaa 预处理后 ^#a#a#$正确答案是 aa。这两个过了说明定义和换算基本自洽。5.2 镜像下标越界与 min 的边界当 i 落在 mx 之外时2*id-i可能是个负数或者超出数组范围所以必须先判断i mx再取镜像。我见过有人把判断写成i mx结果在 imx 时取了个无效镜像p 值偏大答案跟着错。记住 mx 是不包含的右边界imx 时已经不在回文覆盖范围内必须走 else 分支从 1 开始。5.3 哨兵缺失导致的越界崩溃如果不加 ^ 和 $while 循环在扩展到字符串边界时会访问 t[-1] 或 t[n]行为未定义可能崩溃也可能读到脏数据。加了哨兵之后最左扩展到 ^ 就停因为 ^ 不等于任何 # 或原字符最右扩展到 $ 就停。这个技巧能省掉循环里两个边界判断代码更短也更快。5.4 常见问题速查表现象可能原因排查方法答案长度总是差 1半径定义与换算公式不匹配用 a、aa 两个最小用例验证偶数长度回文答案错误start 计算用了负数除法改用 (center-maxLen1)/2程序崩溃或乱码缺少哨兵while 越界检查预处理串首尾是否有不同哨兵结果偏短镜像初始值取了 p[j] 未取 min检查是否写了 min(p[2*id-i], mx-i)结果偏长mx 更新条件写错确认是 ip[i] mx 而非 全相同串超时误用了 O(n²) 的中心扩展确认 while 内没有重复扫描5.5 几个我踩过的坑第一个坑是预处理串的下标从 0 还是从 1 开始。我一开始图省事从 0 开始放 #结果镜像公式 2*id-i 在边界上老是差一。后来统一从 1 开始放有效字符0 放哨兵所有公式都顺了。这个纯属工程习惯但能省很多调试时间。第二个坑是 maxLen 的更新时机。我最初把更新放在 while 之前结果记录的是初始半径而不是扩展后的半径答案偏短。正确做法是在 while 和 mx 更新之后用最终的 p[i] 去比较。第三个坑是关于空串和单字符的边界处理。空串直接返回空单字符直接返回它本身这两个特判加上去之后主逻辑就不用操心退化情况。虽然理论上主逻辑也能处理但特判能让代码意图更清晰也避免一些下标计算的边角问题。6. 从马拉车延伸出去的几个实用场景马拉车不只是求最长回文子串。它的半径数组 p 实际上记录了以每个位置为中心的所有回文信息这个信息量比单个最长答案大得多。比如统计回文子串的总数只需要把每个中心的 p[i]/2 累加预处理串半径换算回原串的回文个数一趟扫描就出来了。再比如判断某个区间是否是回文也可以用 p 数组 O(1) 查询。还有一个常见变体是求最长回文前缀或最长回文后缀这类问题用马拉车同样能线性解决只要在扫描时额外判断回文是否触及字符串边界即可。我在做一个文本对称性检测的小工具时就用到了这个思路比反复调用字符串比较函数快了一个数量级。需要提醒的是马拉车解决的是连续子串的回文问题如果是子序列回文可以不连续那就得换动态规划或者区间 DP复杂度 O(n²)两者不要混淆。我见过有同学拿马拉车去解子序列回文的题怎么调都不对本质上是问题建模错了。最后分享一个调试技巧把预处理串、p 数组、mx 和 id 在每个循环迭代后打印出来拿一个短串比如 abacaba手工对一遍你会非常直观地看到镜像复用是怎么发生的、mx 是怎么一步步向右推进的。这个笨办法比看十篇博客都管用我当年就是靠手推三遍才真正把马拉车刻进脑子里。
