647. 回文子串

发表于 2026-01-19 分类于力扣阅读次数： Waline：本文字数： 1.2k 阅读时长 ≈ 4 分钟

考点

区间DP
回文串

回文子串计数问题的三种经典解法

问题描述

给定一个字符串 \(s\)，统计其中 回文子串 的数量。子串要求连续，且单个字符本身也视为回文。

方法一：Manacher 算法（线性时间）

1. 建模思想

Manacher 算法通过 字符串变换 将：

奇数长度回文
偶数长度回文

统一转化为 以单个中心扩展的奇数回文问题。

构造新字符串： \[ s = a_1 a_2 \dots a_n \quad\Rightarrow\quad str = \# a_1 \# a_2 \# \dots \# a_n \# \] 这样，每个回文都对应于 str 中某个中心位置的对称扩展。

2. 状态定义

定义数组： \[ f[i] = \text{以 } i \text{ 为中心的最大回文“半径”} \] 含义是：在 str 中，区间 \([i - f[i] + 1,\, i + f[i] - 1]\) 是回文。

3. 状态转移（核心思想）

维护当前已知的 最右回文区间 \([c - (r-c), r]\)：

c：该回文的中心
r：该回文的最右端点

当 \(i \le r\) 时，可利用对称点： \[ f[i] = \min\bigl(r - i + 1,\; f[2c - i]\bigr) \] 否则从最小半径 1 开始暴力扩展。

4. 回文计数方式

在插入 # 后的字符串中：

每 增加 2 的半径，对应原串 新增一个回文子串
因此当前位置的贡献为：

\[ \left\lfloor \frac{f[i]}{2} \right\rfloor \]

5. 复杂度分析

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

6. 对应代码（已注释）

class Solution {
public:
    int countSubstrings(string s) {
        // 构造插入 '#' 的新字符串
        string str = "#";
        for (int i = 0; i < s.size(); ++i)
            str.push_back(s[i]), str.push_back('#');

        int n = str.size();
        int f[2005] = {};     // f[i]: 以 i 为中心的最大回文半径
        int c = 0, r = 0;     // 当前最右回文的中心和右端点
        int ans = 0;

        for (int i = 1; i <= n; ++i) {
            // 利用对称性初始化
            f[i] = (i <= r) ? min(r - i + 1, f[2 * c - i]) : 1;

            // 向两侧扩展
            while (i - f[i] >= 1 && i + f[i] <= n &&
                   str[i - f[i] - 1] == str[i + f[i] - 1]) {
                ++f[i];
            }

            // 更新最右回文
            if (i + f[i] - 1 > r) {
                c = i;
                r = i + f[i] - 1;
            }

            // 统计贡献
            ans += f[i] / 2;
        }
        return ans;
    }
};

方法二：区间动态规划（二维 DP）

1. 建模思想

将问题建模为： 判断任意子串 \(s[i \dots j]\) 是否为回文。

2. 状态定义

\[ f[i][j] = \begin{cases} 1 & \text{若 } s[i \dots j] \text{ 是回文} \\ 0 & \text{否则} \end{cases} \]

3. 状态转移方程

\[ f[i][j] = \bigl(s[i] = s[j]\bigr) \;\land\; \Bigl(j - i = 1 \;\lor\; f[i+1][j-1]\Bigr) \]

解释：

两端字符必须相等
长度为 2 时直接成立
否则依赖内部子串是否为回文

4. 遍历顺序

由于依赖 \(f[i+1][j-1]\)，需要：

\(i\) 从大到小
\(j\) 从小到大

确保转移时子问题已被计算。

5. 复杂度分析

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

6. 对应代码（已注释）

class Solution {
public:
    static const int maxn = 1e3 + 5;

    int countSubstrings(string s) {
        bool f[maxn][maxn] = {};  // f[i][j]: s[i..j] 是否为回文
        int n = s.size();
        int ans = 0;

        // 长度为 1 的子串
        for (int i = 1; i <= n; ++i) {
            f[i][i] = 1;
            ++ans;
        }

        // 区间 DP
        for (int i = n; i >= 1; --i) {
            for (int j = i + 1; j <= n; ++j) {
                if (s[i - 1] == s[j - 1] &&
                    (j - i == 1 || f[i + 1][j - 1])) {
                    f[i][j] = 1;
                    ++ans;
                }
            }
        }
        return ans;
    }
};

方法三：中心扩展法（无显式 DP）

1. 建模思想

每一个回文子串都存在一个中心：

奇数长度：中心是某个字符
偶数长度：中心是两个字符之间

对每个可能的中心向两侧扩展即可。

2. 等价“状态”理解

虽然没有显式 DP，但可视为：

对每个中心点，求其能扩展出的最大回文区间数

每成功扩展一次，即得到一个新的回文子串。

3. 扩展方式

对位置 \(i\)：

奇数回文： \[ (l, r) = (i-1, i+1) \]
偶数回文： \[ (l, r) = (i, i+1) \]

不断比较 s[l] == s[r]。

4. 复杂度分析

时间复杂度：\(\mathcal{O}(n^2)\)（最坏情况如 "aaaaa"）
空间复杂度：\(\mathcal{O}(1)\)

5. 对应代码（已注释）

class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size();
        int ans = 0;

        for (int i = 1; i <= n; ++i) {
            // 单字符回文
            ++ans;

            // 奇数长度回文扩展
            int l = i - 1, r = i + 1;
            while (l >= 1 && r <= n && s[l - 1] == s[r - 1]) {
                ++ans;
                --l;
                ++r;
            }

            // 偶数长度回文扩展
            l = i;
            r = i + 1;
            while (l >= 1 && r <= n && s[l - 1] == s[r - 1]) {
                ++ans;
                --l;
                ++r;
            }
        }
        return ans;
    }
};

方法对比总结

方法	时间复杂度	空间复杂度	特点
Manacher	\(O(n)\)	\(O(n)\)	理论最优，常数与实现复杂
区间 DP	\(O(n^2)\)	\(O(n^2)\)	建模清晰，适合教学
中心扩展	\(O(n^2)\)	\(O(1)\)	实现最简洁，实践常用

结论：

注重算法理论与极限性能：Manacher
注重建模与可读性：区间 DP
注重工程实现与直观性：中心扩展法