Manacher 算法如何在线性时间求最长回文子串？

简化版

Manacher 用“已知最右回文区间”的对称性复用信息，把每个中心的回文半径计算到均摊 O(1)，整体 O(n)。先在字符间插入分隔符，把奇偶长度回文统一成奇数长度，再维护中心 center、右边界 right 和半径数组 p。

详细版

普通中心扩展每个中心都向两边扩，最坏 O(n^2)。Manacher 的关键是：如果当前位置 i 在当前最右回文右边界内，那么它关于 center 的镜像点 mirror 已经算过半径，可以先继承一部分，再只扩展未确认的新区域。

int longestPalindromeLength(String s) {
    char[] t = preprocess(s).toCharArray();
    int[] p = new int[t.length];
    int center = 0, right = 0, ans = 0;
    for (int i = 0; i < t.length; i++) {
        int mirror = 2 * center - i;
        if (i < right) p[i] = Math.min(right - i, p[mirror]);
        while (i - p[i] - 1 >= 0 && i + p[i] + 1 < t.length
                && t[i - p[i] - 1] == t[i + p[i] + 1]) {
            p[i]++;
        }
        if (i + p[i] > right) {
            center = i;
            right = i + p[i];
        }
        ans = Math.max(ans, p[i]);
    }
    return ans;
}

String preprocess(String s) {
    StringBuilder sb = new StringBuilder("#");
    for (char c : s.toCharArray()) sb.append(c).append('#');
    return sb.toString();
}

插入 # 后，原串最长回文长度等于处理串里的最大半径 ans。

完整版教学

一、为什么中心扩展会重复工作

中心扩展很直观：每个位置作为中心向左右扩。但如果字符串是 "aaaaaa"，每个中心都能扩很远，大量区间被重复比较。

Manacher 想复用的信息是：如果一个大回文已经覆盖了当前位置，那么当前位置附近的局部回文形态和它的镜像位置相关。

大回文:     a b a c a b a
center:          c
i 在右半边，mirror 在左半边

镜像位置算过的半径，可以给 i 一个安全的初值。

二、为什么要插入分隔符

原串里有奇数回文 "aba"，也有偶数回文 "abba"。如果分别处理，代码容易分叉。插入 # 后：

aba  -> #a#b#a#
abba -> #a#b#b#a#

所有回文都变成以某个字符为中心的奇数长度回文。这样半径数组 p[i] 的语义统一：在处理串中以 i 为中心能向外扩多少步。

记忆钩子：插入分隔符不是为了改变答案，而是为了让奇数回文和偶数回文共用同一套中心半径定义。

原串	处理串	统一后的中心
`"aba"`	`#a#b#a#`	字符 `b`
`"abba"`	`#a#b#b#a#`	中间的 `#`
`"a"`	`#a#`	字符 `a`

三、`center` 和 `right` 表示什么

遍历到位置 i 时，维护一个目前能到达最右侧的回文区间：

center = 目前最右回文的中心
right  = 这个回文的右边界

如果 i < right，说明 i 落在这个已知回文内部。设 mirror = 2 * center - i，它是 i 关于 center 的对称点。

四、为什么能继承镜像半径

因为 center 对应的是回文区间，左半边和右半边对称。mirror 的回文半径有一部分可以映射到 i。

但继承不能超过右边界：

if (i < right) {
    p[i] = Math.min(right - i, p[mirror]);
}

如果 p[mirror] 完全在大回文内部，直接继承；如果碰到左边界，那么右侧对应部分还没被验证，只能继承到 right - i，再继续扩。

五、扩展只验证未知区域

拿到初始半径后，继续比较 i - p[i] - 1 和 i + p[i] + 1。这一步只发生在当前半径之外，也就是之前没有被当前中心证明过的区域。

while (left >= 0 && rightIndex < t.length && t[left] == t[rightIndex]) {
    p[i]++;
}

每次真正扩展成功，都可能推动全局 right 向右走。right 最多走到处理串末尾，所以整体是线性的。

六、如何从处理串长度还原答案

在 #a#b#a# 中，以 b 为中心的半径是 3，对应原串 "aba" 长度也是 3。插入分隔符后，最大半径刚好等于原串回文长度。

如果要返回子串，还要记录最佳中心 bestCenter 和半径 bestLen：

start = (bestCenter - bestLen) / 2
answer = s.substring(start, start + bestLen)

这个公式来自处理串坐标到原串坐标的压缩：每两个处理串位置对应原串一个字符跨度。

七、常见误区与追问

误区：right 写成闭区间和开区间混用。 本文写法中 right 是当前回文能覆盖到的最右下标，更新和判断必须一致。
误区：继承 p[mirror] 时不取 min。 镜像半径可能越过右边界，越过部分没有被证明。
误区：插入分隔符后答案长度再除以 2。 本文半径定义下最大 p[i] 就是原串长度，不需要再除。
追问：为什么 Manacher 是 O(n)？ 每次额外扩展成功都会推动右边界，右边界总推进次数线性。
追问：它和中心扩展的区别是什么？ 中心扩展每个中心从零开始，Manacher 用镜像半径给初值。
追问：如何返回最长回文子串而不只是长度？ 记录最佳中心和半径，用 (center-len)/2 转回原串起点。

八、加强记忆

Manacher 可以记成“加井号统一奇偶，靠镜像复用半径，只扩未知边界”。center/right 是全局最右回文，mirror=2*center-i 是局部答案的提示，min(right-i, p[mirror]) 是安全继承。面试里不必背玄学公式，要把“继承不能越过已证明边界”说清楚。

简化版

详细版