我的算法书 - Manacher：线性时间最长回文子串

一句话算法

Manacher 把奇偶回文统一成一种形式，并用“镜像半径”跳过已经证明相等的部分，只在右边界外继续扩展。

问题模型

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

回文串指正着读和反着读完全相同的字符串，例如：

aba
abba
anana

朴素做法枚举每个中心并向两侧扩展。中心有 $O(n)$ 个，每次扩展最坏 $O(n)$ ，总复杂度 $O(n^2)$ 。

Manacher 将这个问题优化到 $O(n)$ 。

核心直觉

回文串有对称性。若我们已经知道某个中心 center 的回文区间最右端为 right，那么区间内部的新位置 i，可以先看它关于 center 的镜像点：

mirror = 2 * center - i

镜像点已经算过回文半径，所以 i 至少可以继承一部分半径，不需要从 0 开始重新比较。

另一个问题是奇偶回文分裂：

aba   -> 奇数长度回文
abba  -> 偶数长度回文

Manacher 在字符之间插入 #，把它们都变成奇数长度回文：

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

这样代码只需要处理一种中心。

算法步骤

预处理字符串：
- 在字符之间插入 #；
- 在两端加入不同哨兵，防止扩展越界。
维护数组 p[i]，表示处理后字符串中以 i 为中心的回文半径。
维护当前最右回文区间：
- center：该区间中心；
- right：该区间右边界。
枚举每个中心 i：
- 若 i < right，用镜像点 mirror = 2 * center - i 初始化 p[i]；
- 再从当前半径开始继续向两边扩展；
- 若 i + p[i] 超过 right，更新 center 和 right。
在所有 p[i] 中取最大值，映射回原字符串位置。

算法证明

关键不变量：枚举到位置 i 时，right 是当前已经处理过的回文中最靠右的边界。

若 i < right，说明 i 落在当前最右回文区间内部。由于回文区间关于 center 对称，i 的镜像点 mirror 已经拥有一段可复用的回文半径。

有两种情况：

p[mirror] 完全落在当前最右回文区间内，那么 p[i] = p[mirror] 直接成立。
p[mirror] 超出当前最右回文区间，那么 i 至少能继承到 right - i，超出的部分必须重新比较。

因此初始化：

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

是安全的，不会漏掉答案。随后继续暴力扩展，直到不能扩展为止，所以每个中心的最终半径正确。

时间复杂度的直觉是：right 只会向右移动。每次成功扩展都会推动 right，失败扩展每个中心最多发生一次，所以总比较次数是线性的。

复杂度分析

设原字符串长度为 $n$ 。

预处理后字符串长度为 $O(n)$ 。
Manacher 主循环时间复杂度： $O(n)$ 。
空间复杂度： $O(n)$ 。

代码实现

模板输入一个不含空格的字符串，输出最长回文子串长度和这个子串。

C++

cpp

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

        #include <bits/stdc++.h>
using namespace std;

constexpr int MAXN = 110000;            // 原始字符串最大长度

// Manacher 模板（不使用 std::string）
struct Manacher {
    // 变换后长度上限：2*MAXN + 少量哨兵
    static const int SZ = MAXN * 2 + 5;
    char t[SZ];    // 变换后的字符串：^ # a # b # ... # $
    int p[SZ];     // 半径数组（在 t 上的扩展长度）
    int m = 0;     // t 的实际长度（含终止符）

    // 构造变换串并计算 p[]
    // 输入：C 风格字符串 s（以 '\0' 结尾）
    void build(const char *s) {
        int n = (int)strlen(s);
        int k = 0;
        t[k++] = '&';   // 左哨兵，防止越界
        t[k++] = '#';
        for (int i = 0; i < n; ++i) {
            t[k++] = s[i];
            t[k++] = '#';
        }
        t[k++] = '^';   // 右哨兵
        t[k] = '\0';
        m = k;

        // 初始化半径数组
        memset(p,0,sizeof(p));

        // Manacher 主循环
        int center = 0, right = 0;
        for (int i = 1; i < m - 1; ++i) {
            int mirror = 2 * center - i;
            if (i < right) p[i] = min(right - i, p[mirror]);
            else p[i] = 1; // 长度至少是1

            // 暴力扩展：安全因为有哨兵
            while (t[i + p[i]] == t[i - p[i]]) ++p[i];

            // 更新中心与右边界
            if (i + p[i] > right) {
                center = i;
                right = i + p[i];
            }
        }
    }

    // 获取最长回文子串，返回长度；通过引用参数 l,r 返回原串上的左闭右闭索引（0-based）
    int longest(int &l, int &r) const {
        int best_len = 0, best_center = 0;
        for (int i = 1; i < m - 1; ++i) {
            if (p[i]-1 > best_len) {
                best_len = p[i]-1;
                best_center = i;
            }
        }
        if (best_len == 0) { l = 0; r = -1; return 0; }
        // 将 t 中的位置映射回原串的索引
        l = (best_center - best_len) / 2;
        r = l + best_len - 1;
        return best_len;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    static char s[MAXN + 5];
    if (scanf("%s", s) != 1) return 0;   // 读取一个单词（竞赛常用）
    // 若需读取整行（含空格），使用 fgets 或 fgets + 去除末尾换行

    Manacher man;
    man.build(s);

    int L, R;
    int len = man.longest(L, R);
    printf("%d\n", len);
    if (len > 0) {
        // 输出子串：注意 printf 的 %.*s 用法
        printf("%.*s\n", len, s + L);
    }
    return 0;
}

Python

C++ 的 len、l、r 引用出参改为返回元组；定长数组改为按串长动态分配。

python

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

        # Manacher：线性时间求最长回文子串。
# build(s) 后 longest() 返回 (长度, l, r)，[l, r] 是原串上的 0-based 闭区间；
# 无回文（空串）时返回 (0, 0, -1)。C++ 用 int& 出参，Python 改为元组返回。
# 变换串为 & # c1 # c2 # ... # ^，两端哨兵互不相等，扩展时无需判边界。
# C++ 用定长数组 MAXN=110000，Python list 按 len(s) 动态分配，没有长度上限。

type IntSeq = list[int]  # p：半径数组，p[i] 为变换串上以 i 为中心的扩展长度
type Text = list[str]  # t：变换后的字符序列，首尾各有一个哨兵


class Manacher:
    """t / p / m 与 C++ 成员一一对应；m 是含哨兵的变换串长度。"""

    t: Text
    p: IntSeq
    m: int

    def __init__(self) -> None:
        self.t = []
        self.p = []
        self.m = 0

    def build(self, s: str) -> None:
        """构造变换串并计算半径数组；可对同一对象反复 build 换新串。"""
        # 交错插入 '#' 后，任意回文长度都是奇数，一个数组即可同时处理奇偶回文。
        t: Text = ["&", "#"]
        for ch in s:
            t.append(ch)
            t.append("#")
        t.append("^")
        self.t = t
        self.m = len(t)
        self.p = [0] * self.m

        center = 0  # 当前已知最靠右回文的中心
        right = 0  # 该回文的右边界（不含）
        for i in range(1, self.m - 1):  # 跳过两个哨兵
            mirror = 2 * center - i  # i 关于 center 的对称点
            if i < right:
                # 对称点的半径受右边界限制，取两者较小值作为初值。
                self.p[i] = min(right - i, self.p[mirror])
            else:
                self.p[i] = 1  # 至少包含 i 自身
            # 暴力扩展；因为哨兵互不相等，最右/最左一定停得住。
            while self.t[i + self.p[i]] == self.t[i - self.p[i]]:
                self.p[i] += 1
            if i + self.p[i] > right:
                center = i
                right = i + self.p[i]

    def longest(self) -> tuple[int, int, int]:
        """返回 (最长回文长度, l, r)；无解返回 (0, 0, -1)。"""
        best_len = 0
        best_center = 0
        for i in range(1, self.m - 1):
            if self.p[i] - 1 > best_len:  # p[i]-1 正是该中心的原串回文长度
                best_len = self.p[i] - 1
                best_center = i
        if best_len == 0:
            return 0, 0, -1
        # 把变换串位置映射回原串下标：中心左侧有 (p[i]-1) 个原字符，间隔是 '#'。
        l = (best_center - best_len) // 2
        r = l + best_len - 1
        return best_len, l, r

测试用例

输入：

banana

输出：

5
anana

解释：banana 的最长回文子串是 anana，长度为 5。

应用分类详解

Manacher 的本质是“快速得到每个中心的最大回文半径”。只要题目围绕回文子串展开，并且需要大量中心扩展，就应该想到它。

一、最长回文子串

典型模式： 给一个字符串，求最长连续回文子串。

识别信号： 题目明确出现“最长回文子串”。

核心建模： 用 Manacher 计算所有中心半径，再取最大值。

应用场景	经典题目	核心思路
最长回文子串模板	luogu-P3805	直接取最大回文半径
普通文本回文检测	LeetCode 5	返回最长回文子串

二、回文半径参与统计

典型模式： 不只要求最长，还要统计满足条件的回文数量或贡献。

识别信号： 出现“所有回文子串”“长度限制”“贡献和”。

核心建模： 每个中心的半径代表以它为中心的多个回文，按半径累加贡献。

应用场景	经典题目	核心思路
回文数量统计	回文计数类题	每个中心贡献由半径决定
固定长度回文判断	查询类题	预处理半径后判断区间是否被某中心覆盖