illegalCreed

中文

English

中文

English

Appearance

Manacher 算法：O(n) 最长回文子串 ​

基于通用算法套路 · 核于 2026-07

速查 ​

  • 目标：给定串 s，O(n) 求出最长回文子串（朴素中心扩展是 O(n²)）。
  • 核心思想：回文有对称性——若已算出以 c 为中心、覆盖 [L, R] 的大回文，则 c 右侧的点 i（i < R）的回文半径，可从镜像点 j = 2c - i 的已知半径借用初值，不必从 0 重新扩展。
  • 预处理（分隔符 #）：在字符之间及首尾插入 #（外加首尾哨兵 ^ / $ 防越界），把奇偶长度统一——预处理后所有回文都以「一个字符位置」为中心，# 中心 ↔ 原串偶长度回文，字符中心 ↔ 奇长度回文。
  • p 数组（回文半径）：p[i] = 预处理后以 i 为中心的最长回文半径（含中心）；原串最长回文子串长度 = max(p) - 1，中心位置 = 取到最大 p[i] 的 i。
  • 加速关键变量：维护「已触及的最右回文右端 R」及其对称中心 C；对每个 i，若 i < R 则 p[i] 初值取 min(p[2C - i], R - i)，否则从 1 起步。
  • O(n) 证明：R 在整个过程中单调右移、总推进 ≤ n；每次「真正向右扩展」一次字符比较都会让 R 右移至少 1，所以扩展比较总次数 ≤ 2n——O(n)。
  • 代码骨架：for (i=1..m-2) 内 p[i] = (i<R) ? min(p[2C-i], R-i) : 1，然后 while 向两侧扩展更新 p[i]，最后若 i+p[i]-1 > R 则更新 C=i, R=i+p[i]-1。
  • 易错：预处理首尾哨兵防越界；R - i 是「到最右端的余量」，取 min 后扩展才安全；还原原串长度别忘了 -1。
  • 对比 Z 函数：两者都是「单调右端点 + 镜像借用 + 摊还 O(n)」——Manacher 借回文对称，Z 函数借前缀匹配段。

一、为什么需要预处理：统一奇偶 ​

朴素中心扩展要分「奇中心」（expand(c, c)）和「偶中心」（expand(c, c+1)）两套逻辑，Manacher 用一个插入分隔符的预处理把两者合并：

原串 s      =  a  b  a
预处理后 t  =  ^  #  a  #  b  #  a  #  $
下标 i      =  0  1  2  3  4  5  6  7  8
  • ^、$ 是首尾哨兵，保证 while 扩展时两侧字符不会越界（哨兵两两不同必然停止）。
  • # 是字符集外的分隔符，把所有原字符隔开。
  • 预处理后，任何回文都以「一个位置」为中心：# 位置作中心对应原串偶长度回文（如 #a#a# 中心是中间的 #），原字符位置作中心对应原串奇长度回文（如 #a#b#a# 中心是 b）。于是奇偶不再需要分类讨论。

预处理后串长 m = 2n + 1（不含哨兵）或 2n + 3（含哨兵 ^$），仍是 O(n)。

二、p 数组：回文半径 ​

定义 p[i] 为预处理后以 i 为中心、包含 i 在内的最长回文半径（即以 i 为中心向两侧能扩展的最大步数 + 1）。一个关键换算：

预处理后以 i 为中心的最长回文，对应原串中长度为 p[i] - 1 的回文子串。

直觉：预处理后每两个原字符之间都多了 #，回文半径里有一半是 #、一半是原字符（中心算一次），折算回原串恰好 p[i] - 1。所以原串最长回文子串长度 = max(p) - 1，取到最大值的位置 i 还原回原串中心即可。

举例：s = "aba"，预处理 t = "^#a#b#a#$"，则 p[4] = 4（以 b 即下标 4 为中心，覆盖 #a#b#a#，半径 4）——p[4] - 1 = 3，正是原串 "aba" 的长度。

三、对称镜像加速：核心三步 ​

Manacher 的高效来自「复用已算结果」。维护两个量：

  • C：当前已知「触及最右」的回文的对称中心。
  • R：该回文的右端点（R = C + p[C] - 1，即以 C 为中心能到的最右）。

对每个新下标 i（从左到右），分三步：

  1. 借初值：若 i < R（i 落在已知大回文内部），则 i 关于 C 的镜像点 j = 2C - i 已算过，p[i] 至少为 min(p[j], R - i)——取 R - i 是因为「超过 R 的部分无法保证对称，只能老老实实扩展」。若 i >= R 则没有可借的，p[i] 从 1 起步。
  2. 向两侧扩展：从借来的初值开始，while (t[i+p[i]] === t[i-p[i]]) p[i]++——这里靠首尾哨兵 ^$ 保证不会越界。
  3. 更新 C、R：若 i + p[i] - 1 > R（即 i 的回文触及了更右），就更新 C = i, R = i + p[i] - 1。
js
// Manacher 求最长回文子串长度（返回长度，亦可记录中心还原子串）
function manacher(s) {
  // 1. 预处理：插入 # + 首尾哨兵
  const t = ['^', '#'];
  for (const ch of s) { t.push(ch); t.push('#'); }
  t.push('$');
  const m = t.length;
  const p = new Array(m).fill(0);
  let C = 0, R = 0;                  // 当前最右回文的中心、右端
  for (let i = 1; i < m - 1; i++) {
    const mirror = 2 * C - i;        // i 关于 C 的镜像
    if (i < R) p[i] = Math.min(p[mirror], R - i); // 借初值
    while (t[i + p[i]] === t[i - p[i]]) p[i]++;   // 向两侧扩展（哨兵保证停止）
    if (i + p[i] - 1 > R) { C = i; R = i + p[i] - 1; } // 更新最右
  }
  let maxLen = 0, center = 0;
  for (let i = 1; i < m - 1; i++) if (p[i] > maxLen) { maxLen = p[i]; center = i; }
  // 原串最长回文子串长度 = maxLen - 1
  return maxLen - 1;
}

四、O(n) 摊还分析 ​

为什么上述 while 扩展的总比较次数是 O(n)？关键在 R 的单调性：

  • 每次 while 成功匹配（t[i+p[i]] === t[i-p[i]] 成立）一次，都意味着以 i 为中心的回文右端 i + p[i] - 1 至少把 R 推到更右的位置——而 R 上界是 m（O(n)），最多右移 n 次。
  • 借初值（min(p[mirror], R-i)）保证了「在 R 以内的比较不需要重复做」——那些失败的比较（while 退出那一次）每个 i 最多 1 次。

所以「成功的字符比较」≤ n 次（每次都伴随 R 右移），「失败的比较」≤ n 次（每个 i 一次），总计 ≤ 2n 次字符比较——O(n)。这与 Z 函数、KMP 的线性证明是同一个「单调右端点摊还」模板。

五、还原原串：从 p 到子串 ​

求出 maxLen 和 center 后，原串中最长回文子串的中心与长度：

  • 预处理后长度 maxLen（含中心的半径），原串对应回文长度 = maxLen - 1。
  • 预处理后中心 center，原串对应回文的起始下标 = (center - maxLen) / 2（center - maxLen 是预处理串里回文左端，除 2 还原回原串下标）。
js
const start = (center - maxLen) / 2;   // 原串起始下标
const longest = s.slice(start, start + maxLen - 1);

举例 s = "babad"：最长回文是 "bab" 或 "aba"，maxLen = 4（预处理后半径），原串长度 3，与预期一致。

交互演示 ​

下一步 ​

掌握了 Manacher 用「对称性」加速后，下一步是另一条独立的线性算法线——Z 函数（扩展 KMP），它用「已算前缀匹配段（Z-box）」做镜像加速，思想同源但应用场景（匹配、最小周期）不同。