题目

思路

一句话：回文关于中心对称，枚举所有可能的中心并向两侧扩展，每对齐一层就算出一个回文。

最直白的做法：枚举所有子串 s[i..j]（约 O(n²) 个），再对每个子串 O(n) 判断是否回文，总共 O(n³)。n = 1000 时接近 10⁹ 量级，会超时；而且大量子串翻来覆去地重复同一套比较。

关键观察：回文不是“任意两个字符配对”，而是围绕一个唯一轴心镜像相等。只要确定了轴心，就能把“判断是否回文”和“继续往外找新的回文”合并成一次扫描；一旦两端失配，再往外也不可能回文，直接停。

中心分两类：

• 奇数长度：轴落在某个字符上，初始左右指针同为 (i, i)。
• 偶数长度：轴落在 s[i] 与 s[i+1] 之间的缝隙，初始为 (i, i+1)。

共有 2n−1 个中心，每个中心最多向外扩展 O(n) 次，总时间 O(n²)、空间 O(1)。比暴力少一个维度，且无需额外数组。

同一个“大回文由小回文推出”的信息也能写成 DP：dp[i][j] 表示 s[i..j] 是否回文，时间也是 O(n²)。本文主解法选代码最短、空间 O(1) 的中心扩展；DP 与线性 Manacher 见「扩展三」。

解法

封装一个函数 expand(l, r)：只要 s[l] == s[r] 且两端都没越界，就说明又找到一个回文，计数加一，然后左指针左移、右指针右移；失配或越界立即停止。

外层对每个位置 i 调用两次：

1. expand(i, i)：统计以字符 s[i] 为中心的奇数长度回文。
2. expand(i, i+1)：统计以 i 与 i+1 之间缝隙为中心的偶数长度回文。

以 s = "abba" 为例：

合计 1+0+1+2+1+0+1 = 6。注意 i = n−1 时 (i, i+1) 的右端越过右边界，while 一进来就退出、自然计 0，不必特判。

下图把上面 2 个步骤串成流程，并逐步演示：