manacher（马拉车）算法讲解

做 LeetCode 第 5 题「最长回文子串」时，中心拓展能写，但最坏要 O(n²)。马拉车就是把「以每个位置为中心能扩多远」这件事，用一次线性扫描算出来。

如果你已经看过 【leetcode】5. Longest Palindromic Substring最长回文子串，这篇会更聚焦算法本身；如果还没写过那题，看完这篇再回去写题也来得及。

中心拓展卡在哪

回文串左右对称。中心拓展的做法是：枚举每个中心，向两边扩，看能匹配多长。

麻烦在于中心有两种——奇长度回文以某个字符为中心，偶长度回文以两个字符之间的缝隙为中心。所以光枚举中心就要 O(n)，每次最坏再扩 O(n)，整体 O(n²)。

马拉车的思路很直接：先把奇偶两种情况统一成一种，再想办法避免重复比较。

预处理：插入 #

在字符之间插入 #，把 abc 变成 #a#b#c#。

这样任意回文子串在新串里都有一个「正中间的字符」当中心，不用再分奇偶两套逻辑。代价是新串长度变成 2n+1，但仍是线性级别。

半径数组 p[i] 是什么

p[i] 表示：以位置 i 为中心，最多能向左右各扩几个字符（不算中心本身）。

例如 #a#b#a# 里，中间的 b 对应 p[i]=2，还原到原串就是 aba。

右边界 max_right 与镜像复用

马拉车维护两个变量：

• center：当前已知「右端点最远」的那个回文中心
• max_right：该中心能覆盖到的最右下标，即 center + p[center]

扫描到位置 i 时，如果 i < max_right，说明 i 落在某个「已经探过的回文臂」里面。此时 i 关于 center 的镜像点 mirror = 2 * center - i 已经算过 p[mirror]，可以先抄一部分：

p[i] = min(max_right - i, p[mirror])

min 的两项含义分别是：

• p[mirror]：镜像点能扩多远，理论上对称位置也能扩这么远
• max_right - i：但右臂不能超过当前已知的右边界，否则就是越界假设

抄完之后还不够，还要像中心拓展一样继续尝试向外扩，直到字符不等或越界。

完整 Python 实现

下面代码可直接用于 LeetCode 5，注释对应上面的变量含义：

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if len(s) < 2 or s == s[::-1]:
            return s

        t = "#" + "#".join(s) + "#"
        t_len = len(t)
        p = [0] * t_len

        max_right = 0
        center = 0
        max_len = 1
        start = 0

        for i in range(t_len):
            if i < max_right:
                mirror = 2 * center - i
                p[i] = min(max_right - i, p[mirror])

            left = i - (1 + p[i])
            right = i + (1 + p[i])

            while left >= 0 and right < t_len and t[left] == t[right]:
                p[i] += 1
                left -= 1
                right += 1

            if i + p[i] > max_right:
                max_right = i + p[i]
                center = i

            if p[i] > max_len:
                max_len = p[i]
                start = (i - max_len) // 2

        return s[start: start + max_len]

还原下标时，start = (i - max_len) // 2 是把预处理串的位置映射回原串起点，别手推时搞混就行。

复杂度与适用场景

• 时间 O(n)：每个位置最多被「真扩」常数次
• 空间 O(n)：p 数组和预处理串

实际刷题里，字符串不长时中心拓展也够；数据变大、或者同一套回文逻辑要写很多遍时，马拉车值得背下来。

回文相关题如果还要计数、判合法串，往往还是中心拓展或 DP 更顺手；只求最长回文子串，马拉车就是经典正解。

版权声明: 本文首发于 指尖魔法屋-manacher（马拉车）算法讲解（https://blog.thinkmoon.cn/post/737_manacher_%E9%A9%AC%E6%8B%89%E8%BD%A6_%E7%AE%97%E6%B3%95%E8%AE%B2%E8%A7%A3/） 转载或引用必须申明原指尖魔法屋来源及源地址！