M647.回文子串

双指针（中心扩展），dp（Manacher，马拉车算法），https://leetcode.cn/problems/palindromic-substrings/

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

示例 1：

输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"

示例 2：

输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

提示：

1 <= s.length <= 1000
s 由小写英文字母组成

这个题目主要体现的是算法，典型数据结构题题目涉及：频繁插入/删除 → 需要链表、平衡树，区间查询 → 需要线段树、树状数组，最短路径 → 需要图+优先队列。

这题是典型的“回文中心扩展”问题。字符串长度 ≤ 1000，用 中心扩展法 O(n²) 就足够了，而且代码非常简洁。

解法：中心扩展（推荐，面试最优雅）

核心思想：

每个回文串都有一个“中心”
回文中心有两种：
1. 单字符中心（奇数长度）→ "aba"
2. 双字符中心（偶数长度）→ "abba"

长度为 n 的字符串，一共有：

n 个单中心
n-1 个双中心

总共 2n - 1 个中心。

代码实现

python

class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)
        res = 0
        
        # 中心扩展函数
        def expand(left, right):
            count = 0
            while left >= 0 and right < n and s[left] == s[right]:
                count += 1
                left -= 1
                right += 1
            return count
        
        for i in range(n):
            # 奇数长度回文（单中心）
            res += expand(i, i)
            
            # 偶数长度回文（双中心）
            res += expand(i, i + 1)
        
        return res

举例解释

示例 1

s = "abc"

每个字符自己是回文：

"a"
"b"
"c"

总数 = 3

示例 2

s = "aaa"

中心扩展过程：

i=0: "a"
i=1: "a", "aaa"
i=2: "a"
偶数中心:
(0,1): "aa"
(1,2): "aa"

总数 = 6

时间复杂度 每个中心最多扩展 O(n)

空间复杂度 O(1)

Manacher（马拉车）算法 可以把本题从 O(n²) 优化到 O(n)。

一、核心思想

问题本质：

对每个位置，求“以它为中心”的最长回文半径。

普通中心扩展的问题是：

每个中心都要重新向两边扩
有大量重复计算

Manacher 的关键优化：

利用回文的“对称性”避免重复扩展。

二、第一步：字符串预处理

为了统一奇偶回文，我们在字符之间插入 #。

例如：

"aba"   →  "#a#b#a#"
"abba"  →  "#a#b#b#a#"

这样：

所有回文都变成“奇数长度”
每个字符和每个缝隙都成为中心

代码：

python

t = '#' + '#'.join(s) + '#'

三、核心变量

我们维护三个变量：

p[i]  : 以 i 为中心的回文半径（包含自己）
C     : 当前已知回文的中心
R     : 当前已知回文的最右边界

关键对称点：

mirror = 2*C - i

图示结构：

      mirror     C        i
        |        |        |
--------|--------|--------|--------
                R

四、三种情况

当我们遍历到位置 i：

情况1：i 在 R 外

i >= R

无法利用对称性 → 只能暴力扩展

情况2：i 在 R 内

i < R

可以利用对称点：

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

这样避免重复扩展。

情况3：可能突破 R

如果扩展后超出 R：

i + p[i] > R

更新：

C = i
R = i + p[i]

五、完整代码

python

class Solution:
    def countSubstrings(self, s: str) -> int:
        # 1. 预处理
        t = '#' + '#'.join(s) + '#'
        n = len(t)
        
        p = [0] * n
        C = 0  # 当前中心
        R = 0  # 当前最右边界
        res = 0
        
        for i in range(n):
            mirror = 2 * C - i
            
            # 2. 如果在R范围内，先继承最小值
            if i < R:
                p[i] = min(R - i, p[mirror])
            
            # 3. 尝试扩展
            left = i - (p[i] + 1)
            right = i + (p[i] + 1)
            
            while left >= 0 and right < n and t[left] == t[right]:
                p[i] += 1
                left -= 1
                right += 1
            
            # 4. 更新中心和右边界
            if i + p[i] > R:
                C = i
                R = i + p[i]
            
            # 5. 统计答案
            # 每个中心贡献 (p[i] + 1) // 2 个原字符串回文
            res += (p[i] + 1) // 2
        
        return res

六、为什么 (p[i] + 1) // 2？

因为：

插入了 #
有一半是“假的回文”

例如：

t = "#a#b#a#"

如果：

p[i] = 3

表示原字符串中贡献：

(3 + 1) // 2 = 2 个

这是数学映射结果。

七、复杂度分析

方法	时间	空间
中心扩展	O(n²)	O(1)
Manacher	O(n)	O(n)

八、为什么它是 O(n)？

关键在于：

每个字符最多被扩展常数次

因为：

R 只会单调向右移动
不会回退
所有扩展总次数 ≤ 2n

九、举例走一遍

s = "aaa"
t = "#a#a#a#"

p 数组最终：

[0,1,2,3,2,1,0]

统计：

(1+1)//2 =1
(2+1)//2 =1
(3+1)//2 =2
(2+1)//2 =1
(1+1)//2 =1

总和 = 6

十、和中心扩展本质区别

中心扩展：每个中心独立算

Manacher：把“所有中心”放在一个大回文框架中共享信息

这是一种 区间信息复用思想，和很多区间DP题本质类似。

Q：怎么求对称点？

用“距离相等”来推。
假设：i 距离 C 的距离 = d
那么：i = C + d
对称点应该在左边：mirror = C - d
把 d 替换掉：d = i - C
所以：mirror = C - (i - C) = 2*C - i

M647.回文子串 ​

M647.回文子串