如何高效求解最长回文子串：从暴力扩展到Manacher算法优化-js教程-PHP中文网

如何高效求解最长回文子串：从暴力扩展到Manacher算法优化

本文详解最长回文子串问题的常见实现缺陷（如越界、内存溢出），并系统介绍时间复杂度为o(n)的manacher算法原理与工业级实现，附完整可运行代码与关键边界处理说明。

本文详解最长回文子串问题的常见实现缺陷（如越界、内存溢出），并系统介绍时间复杂度为o(n)的manacher算法原理与工业级实现，附完整可运行代码与关键边界处理说明。

原始代码看似直观——对每个中心位置分别向左右扩展以寻找奇数/偶数长度回文，但存在两个致命缺陷：未校验数组边界和未剪枝无效扩展。例如，在 while (string[left] === string[right]) 循环中，当 left 减至 -1 或 right 超出字符串长度时，JavaScript 会访问 undefined，导致隐式类型转换（如 undefined === undefined 恒为 true），从而无限循环、持续创建子串，最终触发堆内存溢出（Out of Memory）。

更深层问题在于算法复杂度：原始方法最坏时间复杂度为 O(n³)（n 次中心遍历 × O(n) 扩展 × O(n) 子串拷贝），且空间开销随子串数量线性增长。对于长字符串（如万级字符），性能与内存均不可接受。

推荐方案：Manacher 算法
该算法通过预处理 + 动态维护“回文半径数组”实现线性时间求解：

预处理：将原字符串 s 转换为 ^#a#b#a#$ 形式，统一奇偶长度，避免分支判断；
核心思想：利用已知回文的对称性，复用左侧镜像位置的计算结果，减少重复比较；
关键变量：center（当前最右回文中心）、right（其右边界）、P[i]（以 i 为中心的回文半径）。

以下是健壮、可直接部署的 Manacher 实现：

function longestPalindromicSubstring(string) {
  if (!string || string.length === 0) return "";

  // 预处理：插入分隔符，统一处理奇偶回文
  const processed = ['^', '#'];
  for (let c of string) {
    processed.push(c, '#');
  }
  processed.push('$');
  const s = processed.join('');

  const n = s.length;
  const P = new Array(n).fill(0); // P[i] 表示以 i 为中心的回文半径（含中心）
  let center = 0, right = 0; // 当前最右回文的中心与右边界

  for (let i = 1; i  right) {
      center = i;
      right = i + P[i];
    }
  }

  // 找到最大半径及其位置
  let maxLen = 0, centerIndex = 0;
  for (let i = 1; i  maxLen) {
      maxLen = P[i];
      centerIndex = i;
    }
  }

  // 将 processed 坐标映射回原字符串坐标
  // 原字符串起始索引 = (centerIndex - maxLen) / 2
  const start = Math.floor((centerIndex - maxLen) / 2);
  return string.substring(start, start + maxLen);
}

// 测试
console.log(longestPalindromicSubstring("abaxyzzyxf")); // "xyzzyx"
console.log(longestPalindromicSubstring("a")); // "a"
console.log(longestPalindromicSubstring("")); // ""

关键注意事项：