我第一次在竞赛题库里看到 L2-008 最长对称子串 这个题号时，第一反应是“这不就是最长回文子串吗？”但如果你只是急着背模板，很容易漏掉这类题真正想考的东西：对称子串的连续区间、奇偶长度的中心差异、以及从暴力到线性的优化路径。
回文这个概念很好懂，正着读和倒着读一样，比如 “aba”“abba”，中文里 “上海自来水来自海上” 也算。但题目一旦从“判断某个串是不是回文”升级成“从一个长串里找出最长的连续对称片段”，难度立刻不一样。对于准备算法面试、竞赛刷题，或者单纯想把字符串基本功打牢的人来说，这道题是绕不开的经典。
这篇文章我会从暴力枚举开始，逐步走到中心扩展、动态规划，最后把 Manacher 算法的思路也拆开讲清楚。过程中会附上可直接运行的代码、我实际踩过的坑，以及调试时常用的小技巧。如果你已经会一种解法，重点可以看各方法的边界条件和复杂度的差距；如果是新手，建议按顺序读完，先从“能跑通”开始，再谈“跑得快”。
1. 题目拆解：先想清楚对称子串的定义
1.1 子串和子序列不是一回事
先说最容易被忽略的定义：题目要求的是“对称子串”，也就是在原字符串中必须连续出现的一段字符。它和“对称子序列”不一样，子序列可以跳过中间字符。比如字符串"abcba"：
- 子串
"abcba"本身对称； - 子串
"bcb"也称； - 但子序列
"aca"（取第 0、2、4 个字符）虽然对称，却不是子串，因为它不连续。
所以做题之前第一件事就是确认输入输出。有些题只要输出最长长度，有些题要求输出具体的子串。L2-008 通常要求返回长度或输出满足条件的子串，不同评测环境要求不一样，但核心思路是一样的：找出满足s[i] == s[j]且中间部分对称的最长区间[i, j]。
1.2 对称子串的两种形态
对称串按长度可以分成两类：
- 奇数长度：中心是一个字符，例如
"aba"的中心是b； - 偶数长度：中心是两个字符之间的空隙，例如
"abba"的中心在b和b之间。
这一步看起来简单，但大量错误都出在这里。很多人写中心扩展时只考虑了奇数长度的中心，导致"abba"这种样例返回"bb"而不是"abba"。后面讲算法时，我会把这两种中心分别处理。
2. 暴力到中心扩展：先做到“能跑通”
2.1 暴力枚举：用最简单的方式验证定义
暴力思路非常直观：枚举所有可能的起点i和终点j，判断s[i:j+1]是否对称，更新最大值。代码如下：
def longest_palindrome_brutal(s: str) -> str: n = len(s) if n < 2: return s start = 0 max_len = 1 for i in range(n): for j in range(i, n): segment = s[i:j+1] if segment == segment[::-1] and j - i + 1 > max_len: max_len = j - i + 1 start = i return s[start:start + max_len]这段代码能跑，但复杂度是 O(n^3)，因为枚举了 O(n^2) 个区间，每个区间判断回文又要 O(n)。当 n 到 1000 左右还能勉强用，到了 5000 以上就会明显吃力。不过它最适合验证你的测试样例：先跑一遍暴力，再拿优化的解法去比对结果，能有效排除边界错误。
2.2 中心扩展：从每个中心向两边扩散
中心扩展的思路是：每个回文串都有一个“中心”，我们从中心开始，同时向左、向右扩展，只要左右字符相等，就继续扩大范围。由于奇数和偶数长度的中心不同，所以每个位置要尝试两种中心：
- 中心是当前位置
i，对应奇数长度回文； - 中心是
i和i+1之间的空隙，对应偶数长度回文。
Python 代码如下：
def longest_palindrome_expand(s: str) -> str: n = len(s) if n < 2: return s start = 0 max_len = 1 def expand(left: int, right: int): # 从 [left, right] 开始向两边扩展，返回有效回文区间的左右下标 while left >= 0 and right < n and s[left] == s[right]: left -= 1 right += 1 return left + 1, right - 1 for i in range(n): # 奇数长度中心：i l1, r1 = expand(i, i) if r1 - l1 + 1 > max_len: max_len = r1 - l1 + 1 start = l1 # 偶数长度中心：i 和 i+1 l2, r2 = expand(i, i + 1) if r2 - l2 + 1 > max_len: max_len = r2 - l2 + 1 start = l2 return s[start:start + max_len]这里expand内部先移动指针再判断，所以退出循环时，left和right已经越界到不合法的位置。返回left + 1, right - 1再还原成合法区间，能避免很多下标错误。
中心扩展的时间复杂度是 O(n^2)，因为一共有2n - 1个中心，每个中心最多向外扩展 O(n) 步。空间复杂度是 O(1)。这是我在面试中优先考虑的手写方案：代码短，不容易写错，而且性能已经能应付大多数场景。
2.3 为什么说中心扩展是“性价比之王”
很多人一上来就想学 Manacher，觉得 O(n^2) 太慢。但实际场景中，n 在几千甚至一万以下时，中心扩展完全够用。它最大的优点是：
- 不需要额外的 DP 表格，空间 O(1)；
- 不需要处理复杂的遍历顺序；
- 思维模型简单：一个回文串就是从中心长出来的。
如果你追求稳妥，这道题用中心扩展就够了。真正需要 Manacher 的场景是字符串长度达到 10^5 甚至 10^6，或者竞赛数据卡得很紧。到那时候再从中心扩展升级到线性算法，理解成本会低很多。
3. 动态规划解法：用一张表记录回文状态
3.1 状态定义与转移方程
动态规划的思路是：用dp[i][j]表示字符串从i到j这一段是否为对称子串。布尔值True表示是，False表示否。
转移方程可以写成：
dp[i][j] = True，当且仅当 s[i] == s[j] 且 j - i <= 2 或 dp[i+1][j-1] 为 True这里j - i <= 2是在处理长度 1 和 2 的边界情况：
- 长度 1：
i == j，单个字符一定对称； - 长度 2：
i + 1 == j，只要两个字符相等就对称； - 长度 3：
i + 2 == j，例如"aba"，只要s[i] == s[j]，中间那个字符不需要判断，所以也归入边界条件。
对应代码：
def longest_palindrome_dp(s: str) -> str: n = len(s) if n < 2: return s dp = [[False] * n for _ in range(n)] start = 0 max_len = 1 for i in range(n): dp[i][i] = True for length in range(2, n + 1): for i in range(n - length + 1): j = i + length - 1 if s[i] == s[j] and (length == 2 or dp[i + 1][j - 1]): dp[i][j] = True if length > max_len: max_len = length start = i return s[start:start + max_len]3.2 遍历顺序是动态规划最常见的一个坑
dp[i][j]依赖的是dp[i+1][j-1]，也就是更短的、向内缩一圈的区间。所以在填充表格时，必须保证较短的区间先被计算出来。
如果你写成下面这种常见的错误方式：
# 错误示范 for i in range(n): for j in range(i, n): if s[i] == s[j] and (j - i <= 2 or dp[i+1][j-1]): ...问题在于：当i从 0 往后推进时，dp[i+1][j-1]可能还没有被计算。比如计算dp[0][4]时，需要dp[1][3]，但内层循环j是从i开始的，dp[1][3]的i=1还没有进入外层循环，表格里是默认的False，导致结果错误。
所以正确的做法是：第一层循环枚举区间长度length，第二层循环枚举起点i。这样所有长度为length-2的短区间一定先被算完。
3.3 空间优化：滚动数组与一维写法
经典的 DP 表格需要 O(n^2) 空间，当 n 是 5000 时，二维布尔数组大概是 2500 万字节，还能接受；但 n 到 10^4 以上，内存就会很紧张。
因为dp[i][j]只依赖dp[i+1][j-1]，也就是长度减少 2 的区间，所以可以只保留最近两层的状态。更常见的做法是只开一维数组，按长度从短到长滚动更新：
def longest_palindrome_dp_rolling(s: str) -> int: n = len(s) if n < 2: return n dp = [False] * n max_len = 1 for length in range(2, n + 1): for i in range(n - length + 1): j = i + length - 1 if length == 2: dp[i] = (s[i] == s[j]) else: dp[i] = (s[i] == s[j]) and dp[i + 1] if dp[i]: max_len = length return max_len这个写法只用一维数组，但有一个细节：dp[i]在更新前存的是“长度为length-2时i到i+length-3是不是回文”的状态；更新后变成“长度为length时i到j的状态”。因为更新是按i从小到大，而dp[i+1]尚未被覆盖或刚好覆盖，这里需要仔细对照，否则容易出错。
我的实际建议是：优先保证正确，空间优化放到第二优先级。如果题目只是让返回长度或输出子串，中心扩展更省事；只有当你明确需要在动态规划的表格上做更多扩展时，二维 DP 才更值得写。
4. Manacher 算法：线性时间解决回文问题
4.1 预处理：插入分隔符统一奇偶
中心扩展之所以是 O(n^2)，是因为每个中心都要向两边扫描，而且奇数长度和偶数长度的中心要分开处理。Manacher 的核心思路是：通过预处理，把偶数长度的回文也变成奇数长度的回文，然后用一种尽量不重复扫描的方式，把所有中心的回文半径记录下来。
预处理的方法是：在原始字符串的每个字符之间以及首尾都插入一个特殊字符，比如#。
例如：
原始串："aba" 预处理后："#a#b#a#"这样一来，原始串里的回文"aba"变成了新串里的#a#b#a#，长度为 7，是奇数；原始串里的回文"abba"会变成#a#b#b#a#，也是奇数长度。所有回文在新串中都有了唯一的中心。
4.2 回文半径数组 p[i] 与最右边界
在预处理后的新串上，定义p[i]表示以位置i为中心的最长回文半径（半径包含中心自己）。
例如新串#a#b#a#：
- 以
b为中心，回文部分是#a#b#a#，p[3] = 4； - 原串中回文
"aba"的长度是 3，正好等于p[i] - 1。
这个规律对所有情况成立：预处理后，原串回文长度 =p[i] - 1。
Manacher 还有一个关键变量是right，表示当前所有已知回文串中，能覆盖到的最右端下标。center表示这个最右回文串的中心。当我们要计算某个位置i的p[i]时，如果i < right，那么可以利用关于center对称的位置mirror = 2 * center - i来初始化。
核心代码：
def longest_palindrome_manacher(s: str) -> str: if len(s) < 2: return s t = '#' + '#'.join(s) + '#' n = len(t) p = [0] * n center = 0 right = 0 max_len = 1 start = 0 for i in range(n): if i < right: mirror = 2 * center - i p[i] = min(right - i, p[mirror]) else: p[i] = 1 while i - p[i] >= 0 and i + p[i] < n and t[i - p[i]] == t[i + p[i]]: p[i] += 1 if i + p[i] > right: center = i right = i + p[i] if p[i] - 1 > max_len: max_len = p[i] - 1 start = (i - p[i] + 1) // 2 return s[start:start + max_len]上面代码中的start = (i - p[i] + 1) // 2是把新串下标映射回原始字符串的起点。很多人在这里直接用(i - p[i]) // 2，在 Python 里当i - p[i]为负数时会因为向下取整得到错误结果。加 1 是为了避免这个坑。
4.3 为什么 Manacher 是 O(n)
Manacher 的线性复杂度来自两个方面：
第一，right是单调递增的。每次p[i]扩展成功，right就会向右移动。整个算法过程中，right最多从 0 移动到n，所以所有 while 循环的扩展操作加起来是 O(n)。
第二，当i < right时，p[i]不是从 1 开始重新扩展，而是直接利用对称位置的回文半径做了一个“已经确认不回文”的初始化。这一步省掉了大量重复比较。
严格来说，Manacher 并不是完全不重复扫描，但每个位置最多作为“成功扩展”的一部分被扫描常数次，总复杂度仍是 O(n)。空间复杂度 O(n)，因为需要存p数组。
4.4 适合用 Manacher 的场景
我在实际刷题中会这样选：
- 字符串长度 ≤ 5000：优先中心扩展，代码短、不容易错；
- 字符串长度 ≤ 10^5：中心扩展可能勉强能过，但要看时限，稳妥起见直接 Manacher；
- 竞赛题卡 O(n^2)：不用犹豫，直接上 Manacher。
Manacher 的难点不在代码本身，而在理解p[i]的含义和start映射。建议先拿"abba"、"abcba"、"a"、"aa"这几个例子在纸上手动填一遍p数组，比看十遍文章都有用。
5. 实操记录：从样例模拟到踩坑清单
5.1 典型的测试用例设计
我在本地调试时，会先准备一组有针对性的测试用例，而不是直接扔一大段随机字符串。推荐这几类：
输入："babad" 输出："bab" 或 "aba" 输入："cbbd" 输出："bb" 输入："a" 输出："a" 输入："ac" 输出："a" 或 "c" 输入："abcde" 输出：任意一个字符 输入："abacdfgdcaba" 输出："aba" 输入："上海自来水来自海上" 输出：整句（中文也能跑，因为字符比较是按 Unicode 来的）为什么要单独测"ac"和"abcde"？因为这两种情况没有长度超过 1 的回文，很多不严谨的中心扩展实现会在返回结果时出现空串或越界。
5.2 四种解法对比
我在同一个环境下做了几组长度测试，大致表现如下：
| 方法 | 时间复杂度 | 空间复杂度 | 长度 1000 | 长度 5000 | 长度 100000 |
|---|---|---|---|---|---|
| 暴力枚举 | O(n^3) | O(1) | 慢 | 极慢 | 不可行 |
| 中心扩展 | O(n^2) | O(1) | 很快 | 可接受 | 慢 |
| 动态规划 | O(n^2) | O(n^2) | 快但占内存 | 内存明显增长 | 不推荐 |
| Manacher | O(n) | O(n) | 快 | 快 | 稳定 |
这里的“可接受”要看评测数据和时间限制。如果时限是 1 秒，长度 5000 的随机串用中心扩展通常能过；如果数据构造得特别差，全是相同字符，中心扩展会退化到最坏 O(n^2)，仍然危险。Manacher 不管输入长什么样，都是线性扫描，所以竞赛中更保险。
5.3 刷题时容易踩的坑
我这些年做这类题，总结出几个高频错误点，列在这里：
- 只返回长度不返回子串，或者反过来，没有多看题目要求；
- 中心扩展只考虑了奇数长度的中心，漏掉
i和i+1之间的偶数中心； - 动态规划遍历长度时，起点
i范围写成range(n)，导致j越界； - Manacher 中
p[i]初始化时忘记区分i < right和i >= right； - 把
p[i]当成原串回文半径，忘记原串长度是p[i]-1。
这些坑不是看出来的，是跑出来的。建议每次写完解法，先用上面的测试用例跑一遍，再提交到评测系统。如果错了，打印dp表或p数组逐行排查，比瞎猜快得多。
6. 常见问题与调试心得
6.1 输入包含空格、标点或中文怎么办
L2-008 这类题默认把输入当作连续字符串，空格和标点也是字符的一部分。比如"ab a"这个串，因为空格不对称，所以最长的对称子串可能是"a"或"aba"？不，"ab a"中"aba"并不连续，因为中间隔着空格，所以最长只能是单个字符。
但有一些变体题会要求“忽略大小写和非字母数字字符”。如果是这种题，我一般先做一次预处理：
import re clean = re.sub(r'[^a-zA-Z0-9]', '', s).lower()然后再对clean求最长对称子串。注意，此时返回的下标是预处理后的下标，不是原串的下标，需要额外维护映射关系。这个细节很容易被忽略。
6.2 动态规划“状态没用上”的典型错误
有同学会写成这样：
for i in range(n): for j in range(i, n): dp[i][j] = (s[i] == s[j]) and (j - i <= 2 or dp[i+1][j-1])这种写法在外层i从小到大时，dp[i+1][j-1]大量未计算，结果会漏掉较长回文。改进方法除了按长度遍历，还可以让外层i从大到小：
for i in range(n - 1, -1, -1): for j in range(i, n): dp[i][j] = (s[i] == s[j]) and (j - i <= 2 or dp[i+1][j-1])这样也能保证dp[i+1][j-1]已经被计算。两种方向都行，但按长度遍历最不容易出问题。
6.3 Manacher 预处理后的下标对应关系
预处理串的下标和原串下标的关系是：
原串下标 idx 对应预处理串下标 2 * idx + 1 预处理串下标 i 对应原串下标 (i - 1) // 2当你在 Manacher 中找到一个回文区间时，不要直接拿i - p[i] + 1去原串里截取。正确做法是算出原串起点start，再根据原来的回文长度max_len截取。
这个映射关系是最容易出错的地方。我调试时会在代码里加一行：
print(f"i={i}, p[i]={p[i]}, start={start}, sub={s[start:start+p[i]-1]}")多打印几个中心，马上能看出问题。
6.4 面试时怎么把它讲清楚
如果面试官让你现场写最长对称子串，我一般不会一上来就写 Manacher，因为手写线性算法容易在边界上翻车。我更推荐这样回答：
先讲暴力思路和中心扩展，说明复杂度是 O(n^2)，代码能正确跑通。然后补一句：“如果字符串长度很大，还可以用 Manacher 优化到 O(n)，核心是维护当前最右回文边界，利用对称位置减少重复比较。”如果面试官追问，再细写 Manacher。这样既展示了扎实的基础，又体现了优化意识。
最后再分享一点我的个人习惯
我刚开始做这道题的时候，总觉得一定要写出最优解才肯罢休，结果在 Manacher 的边界上反复调试，心态很崩。后来我改变策略：先用中心扩展确保能 AC，再在本地把 Manacher 版本调通，最后用同一个测试集做回归。这样既保住了分数，也慢慢理解了线性算法。
另外一个小技巧：如果题目只要求返回最长长度，中心扩展写法还能更简略，不需要记录start，每次更新最大长度即可。代码量少一些，出错概率也低一些。
最长对称子串这道题的精髓，不在于背模板，而在于你能不能用同一套思维串起四种不同复杂度的解法。从暴力的 O(n^3)，到中心扩展和动态规划的 O(n^2)，再到 Manacher 的 O(n)，每一步都是在解决上一步的某个瓶颈。把这些 bottleneck 想清楚，以后遇到再奇怪的字符串问题，你的分析路径都会清晰很多。
