马拉车算法（Manacher's Algorithm）—— O(n) 求最长回文子串

什么是回文串？

回文串（Palindrome） 是指正读和反读都一样的字符串。例如：

• "racecar" — 正反读都是 racecar
• "level" — 正反读都是 level
• "上海自来水来自海上" — 中文回文经典

回文串分为两种：

问题描述

给定一个长度为 $n$ 的字符串 $s$，找出其中最长的回文子串。

这是 LeetCode 第 5 题，也是面试中的经典问题。

暴力解法为什么不够好？

方法一：枚举所有子串

string longestPalindromeBrutal(string s) {
    int n = s.size();
    string ans;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            string sub = s.substr(i, j - i + 1);
            string rev = sub;
            reverse(rev.begin(), rev.end());
            if (sub == rev && sub.size() > ans.size())
                ans = sub;
        }
    }
    return ans;
}

• 子串数量：$O(n^2)$
• 每个子串判断回文：$O(n)$
• 总复杂度：$O(n^3)$ ❌

方法二：中心扩展法

string longestPalindromeCenter(string s) {
    int n = s.size();
    int start = 0, maxLen = 0;
    for (int center = 0; center < n; center++) {
        // 奇数长度
        int l = center, r = center;
        while (l >= 0 && r < n && s[l] == s[r]) {
            if (r - l + 1 > maxLen)
                start = l, maxLen = r - l + 1;
            l--, r++;
        }
        // 偶数长度
        l = center, r = center + 1;
        while (l >= 0 && r < n && s[l] == s[r]) {
            if (r - l + 1 > maxLen)
                start = l, maxLen = r - l + 1;
            l--, r++;
        }
    }
    return s.substr(start, maxLen);
}

• $2n-1$ 个中心，每个中心扩展 $O(n)$
• 总复杂度：$O(n^2)$ — 比暴力好，但还不够快

马拉车算法

Manacher 在 1975 年提出 $O(n)$ 算法，核心思想：

利用已经算好的回文信息，避免重复扩展。

第一步：插入 # 统一奇偶

在每两个字符之间插入 #，不加哨兵：

原串:   a  b  a
处理后:  #  a  #  b  #  a  #

插入后所有回文都变成奇数长度，不再区分奇偶：

原串 "aa"  (偶数) → "#a#a#"    → 中心是中间的 '#'
原串 "aba" (奇数) → "#a#b#a#"  → 中心是 'b'

第二步：回文半径数组 P

P[i] 表示以位置 i 为中心的最长回文半径（包含中心自身）。

处理后:  #  a  #  b  #  a  #
索引:   0  1  2  3  4  5  6
P[i]:   1  2  1  4  1  2  1

• P[3] = 4，以 b 为中心，半径 4，即 #a#b#a#
• P[1] = 2，以 a 为中心，半径 2，即 #a#

原串回文长度 = P[i] - 1

第三步：利用对称性加速

维护两个变量：

• C — 当前最右回文的中心
• R — 该回文的右边界（包含），即 R = C + P[C] - 1

对于当前位置 i，找它关于 C 的对称点：

mirror = 2 * C - i

     mirror       C          i
       ↓          ↓          ↓
.....|.x..........|..........x.|...
     |←P[mirror]→ |← 关于C对称 →|

三种情况：

情况一：i > R（超出右边界）

没法利用已有信息，P[i] = 1，从头扩展。

[───已探索───]
               i
               ↑ 超出 R，暴力扩展

情况二：i <= R 且 P[mirror] < R - i + 1（镜像完全在内部）

直接复用：P[i] = P[mirror]，while 一步都不跑。

[————————————C 的回文————————————R]
   [mirror]             [i]
    ←P[m]→            ←P[i]→     一样长

情况三：i <= R 且 P[mirror] >= R - i + 1（镜像触及边界）

知道至少 R - i + 1，从 R 往后继续扩展。

——————[—————————————C的回文—————————————R]
    [..mirror..]                [...i...]
    ←   太长   →                ←至少R-i+1→    继续扩

代码统一写成：

if (i > R)
    P[i] = 1;                          // 情况一
else
    P[i] = min(R - i + 1, P[mirror]);  // 情况二/三取最小

while (条件)  // 统一扩展，情况二第一次就失败跳过
    P[i]++;

可视化推演

以 s = "ababa" 为例：

处理后:  #  a  #  b  #  a  #  b  #  a  #
索引:   0  1  2  3  4  5  6  7  8  9 10

t = # a # b # a # b # a #
    0 1 2 3 4 5 6 7 8 9 10

i=0: i>R(-1) → 情况一, P[0]=1, 越界停止
     C=0, R=0

i=1: i>R(0)  → 情况一, P[1]=1
     扩展 t[0]=t[2]='#' → P[1]=2, 越界停止
     C=1, R=2
     回文区间 [0,2] = "#a#"

i=2: i≤R(2), mirror=0, R-i+1=1, P[0]=1
     P[2]=min(1,1)=1 → t[1]≠t[3], 停止
     P[2]=1

i=3: i>R(2)  → 情况一, P[3]=1
     扩展 t[2]=t[4]='#', t[1]=t[5]='a', t[0]=t[6]='#' → P[3]=4
     C=3, R=6
     回文区间 [0,6] = "#a#b#a#"

i=4: i≤R(6), mirror=2, R-i+1=3, P[2]=1
     P[4]=min(3,1)=1  (情况二，直接复用)
     扩展第一步即失败, P[4]=1

i=5: i≤R(6), mirror=1, R-i+1=2, P[1]=2
     P[5]=min(2,2)=2  (情况三)
     继续扩展: t[3]=t[7]='b', t[2]=t[8]='#', t[1]=t[9]='a', t[0]=t[10]='#' → P[5]=6
     C=5, R=10
     回文区间 [0,10] = "#a#b#a#b#a#"

...依此类推

最终：

P = [1, 2, 1, 4, 1, 6, 1, 4, 1, 2, 1]

max_element(P) = 6，6 - 1 = 5 → 最长回文 "ababa" ✓

完整代码

int manacher(string s) {
    if (s.empty()) return 0;

    // 1. 预处理：只插入 #
    string t;
    for (char ch : s) {
        t += '#';
        t += ch;
    }
    t += '#';
    // s = "aba" → t = "#a#b#a#"

    int n = t.size();
    vector<int> P(n);
    int C = 0;   // 最右回文的中心
    int R = -1;  // 最右回文的右边界（-1 让 i=0 也走情况一）

    // 2. 计算回文半径
    for (int i = 0; i < n; i++) {
        int mirror = 2 * C - i;

        if (i > R)
            P[i] = 1;                          // 情况一
        else
            P[i] = min(R - i + 1, P[mirror]);  // 情况二/三

        // 中心扩展
        while (i - P[i] >= 0 && i + P[i] < n &&
               t[i - P[i]] == t[i + P[i]])
            P[i]++;

        // 更新最右边界
        if (i + P[i] - 1 > R) {
            C = i;
            R = i + P[i] - 1;
        }
    }

    // 3. max_element 找最大值，-1 即为答案
    return *max_element(P.begin(), P.end()) - 1;
}

复杂度

总结

三步走：

1. 插入 # → 统一奇偶，所有回文变奇数
2. min(R - i + 1, P[mirror]) → 能抄就抄，抄不到的继续扩
3. max_element(P) - 1 → 拿到答案