Manacher 算法：线性时间求最长回文子串

我曾经把“Manacher 算法：线性时间求最长回文子串”学成了一组互不相干的名词和代码。具体表现是：Manacher 的对称半径和右边界曾经让我觉得像技巧题，直到手动画了几个奇偶长度回文，才理解它复用了什么。后来我尝试只保留一个问题：它到底在减少哪一种重复工作？顺着这个问题，整块知识才稳定下来。

Manacher 是专门求回文子串的算法，最经典用途是在线性时间内求最长回文子串。它的核心不是“神奇公式”，而是利用已有回文区间和镜像位置，减少重复扩展。

它从哪里来

Glenn Manacher 在 1975 年提出线性时间回文算法。它通过改造字符串统一奇偶回文，再利用当前最右回文区间的对称信息复用已经得到的半径，避免从每个中心重复向外比较。

回文问题为什么特殊

回文具有中心对称性。普通中心扩展会枚举每个中心，然后向两边扩展，最坏复杂度是 O(n²)。Manacher 通过记录当前最右回文边界，把许多扩展过程复用掉。

统一奇偶长度

字符串有奇数长度回文和偶数长度回文。Manacher 常先插入分隔符，把它们统一。

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

这样每个回文都可以看成以某个位置为中心的奇数长度回文。

回文半径

Manacher 回文半径

图：如果当前位置在已知右边界内，可以先借用镜像位置的回文半径

Manacher 维护两个变量：

center：当前最右回文区间的中心。
right：当前已知回文区间的最右边界。

数组 p[i] 表示以 i 为中心的回文半径。

代码实现

String longestPalindrome(String s) {
    char[] t = transform(s);
    int[] p = new int[t.length];
    int center = 0, right = 0;
    int bestCenter = 0, bestLen = 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];
        }
        if (p[i] > bestLen) {
            bestLen = p[i];
            bestCenter = i;
        }
    }
    int start = (bestCenter - bestLen) / 2;
    return s.substring(start, start + bestLen);
}

char[] transform(String s) {
    char[] t = new char[s.length() * 2 + 1];
    for (int i = 0; i < t.length; i++) {
        t[i] = (i % 2 == 0) ? '#' : s.charAt(i / 2);
    }
    return t;
}

为什么是线性复杂度

虽然代码里有 while 扩展，但 right 只会向右移动，不会反复后退。每次真正扩展成功，都会推动最右边界。因此总扩展次数是线性的。

与中心扩展怎么选择

场景	推荐
面试中快速写出可读解	中心扩展
字符串较短	中心扩展
需要严格线性复杂度	Manacher
多次回文查询	Manacher 或 DP 预处理

我的分析

Manacher 不是每次都必须用。中心扩展简单、好写、容易解释，很多面试场景已经够用。但如果你想把字符串算法体系补完整，Manacher 值得学，因为它代表了一类重要思想：利用对称性和历史边界减少重复判断。

面试题

为什么要在字符串中插入分隔符？
center 和 right 分别表示什么？
Manacher 为什么能做到 O(n)？
中心扩展和 Manacher 怎么选择？
如何从处理后的字符串下标还原原字符串下标？