本文详解最长回文子串问题的常见实现缺陷（如越界、内存溢出），并系统介绍时间复杂度为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 < n - 1; i++) {
const mirror = 2 * center - i;
// 利用对称性初始化 P[i]
if (i < right) {
P[i] = Math.min(right - i, P[mirror]);
}
// 尝试向外扩展（注意：s 已加边界符，无需额外越界检查）
while (s[i + P[i] + 1] === s[i - P[i] - 1]) {
P[i]++;
}
// 更新最右回文信息
if (i + P[i] > right) {
center = i;
right = i + P[i];
}
}
// 找到最大半径及其位置
let maxLen = 0, centerIndex = 0;
for (let i = 1; i < n - 1; i++) {
if (P[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("")); // ""关键注意事项：
- ✅ 预处理字符串首尾添加 ^ 和 $ 作为哨兵，确保 while 循环不会越界；
- ✅ P[i] 存储的是半径长度（即回文总长 = 2 * P[i] + 1），映射回原串时需整除 2；
- ✅ 时间复杂度严格 O(n)：每个字符最多被访问 2 次（一次在扩展中，一次在利用对称性时）；
- ⚠️ 不要省略空值校验（!string）和边界处理（i < n - 1），否则仍可能报错。
总结：解决最长回文子串问题，不应止步于“能跑通”，而需兼顾正确性、鲁棒性与性能。Manacher 算法是经过理论验证与工程检验的最优解，尤其适用于高频调用或大数据量场景。
