5. 最长回文子串

发表于 分类于 阅读次数： Waline： 本文字数： 1k 阅读时长 ≈ 3 分钟

考点

  • 区间DP
  • 回文串
  • Manacher

思路

一、问题描述与建模动机

1. 问题描述

给定一个字符串 \(s\)，需要找出其中最长的回文子串。

  • 回文串的定义：正向与反向读完全相同
  • 子串要求连续

示例：

  • 输入："babad"
  • 输出："bab" 或 "aba"

2. 朴素建模的瓶颈

直观建模方式：

  • 枚举所有子串 \(O(n^2)\)
  • 判断是否为回文 \(O(n)\)

总复杂度： \[ O(n^3) \] 即便通过中心扩展优化到： \[ O(n^2) \] 在 \(n = 1000\) 时仍然处于性能边缘。

3. 核心建模思想：统一回文的奇偶性

回文子串有两种形式：

  • 奇数长度：aba
  • 偶数长度：abba

Manacher 算法的关键建模步骤是：

将“奇回文”和“偶回文”统一成一种形式

扩展字符串建模

在原字符串每个字符之间插入分隔符 #： \[ s = \text{"abba"} \\ \Rightarrow \\ \text{str} = \#a\#b\#b\#a\# \] 性质：

  • 所有回文在扩展串中都变成奇数长度
  • 回文中心一定落在某一个字符位置（包括 #）

这一步是整个算法的建模核心。

二、算法设计（Manacher）

1. 扩展串与下标体系

设：

  • 原串：\(s\)，长度 \(n\)
  • 扩展串：\(\text{str}\)，长度 \(2n + 1\)

构造规则： \[ \text{str} = \#s_0\#s_1\#\cdots\#s_{n-1}\# \] 在实现中采用 1-based 思维 + 0-based C++ 字符串访问：

  • 逻辑下标：i ∈ [1, str.size()]
  • 实际访问：str[i - 1]

2. 回文半径数组的定义

定义数组： \[ f[i] = \text{以 } i \text{ 为中心的回文半径（包含中心）} \] 含义：

  • 初始 \(f[i] = 1\)
  • 回文覆盖区间为：

\[ [i - f[i] + 1,\ i + f[i] - 1] \]

3. 利用回文对称性进行剪枝

维护两个变量：

  • \(c\)：当前最右回文的中心
  • \(r\)：当前最右回文的右端点

对于当前位置 \(i\)：

  • 若 \(i \le r\)，则其关于 \(c\) 的对称点为：

\[ i' = 2c - i \]

此时可直接得到一个最小保证半径： \[ f[i] \ge \min(r - i + 1,\ f[i']) \] 这是 Manacher 算法从 \(O(n^2)\) 降为 \(O(n)\) 的关键设计点。

4. 中心扩展与区间更新

在初始半径的基础上，继续尝试向外扩展： \[ \text{while } \text{str}[i - f[i]] = \text{str}[i + f[i]] \Rightarrow f[i]++ \] 若扩展后： \[ i + f[i] - 1 > r \] 则更新：

  • \(c = i\)
  • \(r = i + f[i] - 1\)

5. 最优解的记录与还原

在遍历过程中维护：

  • \(\text{mx}\)：最大回文半径
  • \(\text{center}\)：对应中心

最终在扩展串中的回文区间为： \[ [\text{center} - f[\text{center}] + 1,\ \text{center} + f[\text{center}] - 1] \] 由于原字符只出现在偶数逻辑下标上，因此：

  • 从左端点 +1 开始
  • 每隔 2 个位置取一个字符
  • 即可恢复原串中的最长回文子串

三、复杂度分析

  • 时间复杂度：\(\mathcal{O}(n)\)
  • 空间复杂度：\(\mathcal{O}(n)\)

四、参考实现（已 AC，逐行注释）

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
class Solution {
public:
    static const int maxn = 1e3 + 5;

    string longestPalindrome(string s) {
        // 1. 构造扩展串：#a#b#c#
        string str = "#";
        for (char chr : s)
            str.push_back(chr), str.push_back('#');

        // center: 当前最长回文的中心
        // mx: 当前最长回文的半径
        // c, r: 当前最右回文的中心与右端点
        int center, mx = 0;
        int c = 0, r = 0;
        int n = str.size();

        // f[i]: 以 i 为中心的回文半径（包含中心）
        int f[maxn << 1];

        // 2. Manacher 主循环（逻辑下标 1..n）
        for (int i = 1; i <= n; ++i) {
            // 初始半径至少为 1（只包含自己）
            f[i] = 1;

            // 若在当前最右回文内部，利用对称性初始化
            if (i <= r)
                f[i] = min(r - i + 1, f[2 * c - i]);

            // 尝试继续向外扩展
            while (i - f[i] >= 1 && i + f[i] <= n &&
                   str[i - f[i] - 1] == str[i + f[i] - 1])
                ++f[i];

            // 若扩展后超过当前最右端点，更新 c 和 r
            if (i + f[i] - 1 > r)
                c = i, r = i + f[i] - 1;

            // 记录最长回文
            if (f[i] > mx)
                mx = f[i], center = i;
        }

        // 3. 从扩展串中恢复原串回文
        string ans;
        // 只取扩展串中偶数逻辑下标对应的原字符
        for (int i = center - f[center] + 2;
             i <= center + f[center] - 1;
             i += 2) {
            ans.push_back(str[i - 1]);
        }

        return ans;
    }
};