Manacher 最长回文子串

字符串 · 回文 · O(n)

换个方向：分析一个串自己的回文结构

前三页 KMP / Rabin-Karp / Boyer-Moore 都在解决「在文本里找模式」。Manacher 换一个方向——分析单个串自己的结构，求它最长的回文子串（正着读反着读一样，如 bab）。朴素做法是枚举每个中心向两边扩展，O(n²)；Manacher 用两个技巧做到 O(n)。

技巧一：插 # 统一奇偶

回文分奇（aba）偶（abba）两种，中心一个在字符上、一个在缝隙里，很烦。办法是在每个字符两侧都插入分隔符 #：babad → #b#a#b#a#d#。这样任何回文都变成奇数长、以某个下标为中心，只需统一处理「以 i 为中心的回文半径 p[i]」。原串里的回文长度恰好等于 p[i]。

技巧二：利用对称性复用

关键在于：维护「目前向右探到最远的那个回文」的中心 C 和右边界 R。当处理新中心 i 且 i < R 时，i 关于 C 有一个镜像点2C−i。因为 [.., R] 是回文，i 附近的情况和镜像点对称——于是 p[i] 可以直接复用min(R−i, p[2C−i])（取 R−i 是因为超出 R 的部分未知、不能照搬），只需再尝试扩展超出 R 的那一点点。已经算过的对称信息不重复算，这就是 O(n) 的来源——和 KMP 用部分匹配表避免回退是同一种智慧。

下面是 babad（转换串 #b#a#b#a#d#）。点「下一步」逐中心看：琥珀环是当前中心 i、蓝环是镜像点、浅蓝带是当前最右回文 [C,R]、绿色是目前最长回文。留意 i=5（复用镜像半径 1 后又扩展到 3）和 i=7（被 R−i 截断）两种情形。走到底，最长回文 = "bab"（长 3）。右侧代码随每一步同步高亮。

预处理：在每个字符两侧插入 # 得到转换串「#b#a#b#a#d#」——长度恒为奇数，把奇/偶回文统一成「以某个下标为中心」

1function manacher(str: string): string {
let t = '#';
for (const ch of str) t += ch + '#';   // 预处理：插 #
const n = t.length;
const p = new Array(n).fill(0);
let c = 0, r = 0;                       // 最右回文中心 c、右边界 r
for (let i = 0; i < n; i++) {
  if (i < r) p[i] = Math.min(r - i, p[2 * c - i]); // 对称性复用
  while (i - p[i] - 1 >= 0 && i + p[i] + 1 < n &&
         t[i - p[i] - 1] === t[i + p[i] + 1]) p[i]++; // 中心扩展
  if (i + p[i] > r) { c = i; r = i + p[i]; }
}
let best = 0, ci = 0;
for (let i = 0; i < n; i++) if (p[i] > best) { best = p[i]; ci = i; }
return str.substr((ci - best) / 2, best);
16}

原串babad

转换串#b#a#b#a#d#

1 / 13

回文问题的基石

最长回文子串 / 子串计数：Manacher 一趟 O(n) 全搞定。
对照三种匹配：KMP/Rabin-Karp/Boyer-Moore 是「文本里找模式」，Manacher 是「单串的回文结构」——都靠复用已算信息避免重复劳动。
更进一步：回文树（PAM）能在线维护一个串的全部回文子串，是回文问题的终极武器。

至此字符串大类四页：三种模式匹配（KMP / Rabin-Karp / Boyer-Moore）+ 一种回文结构分析（Manacher）。它们共同的主题是——用预处理和已知结果，把暴力的重复比较省下来。

算法可视化

Manacher 最长回文子串

换个方向：分析一个串自己的回文结构

技巧一：插 # 统一奇偶

技巧二：利用对称性复用

回文问题的基石