回文串这个题目基本是算法题单里绕不开的常客。无论是准备技术面试、刷题入门还是打算法竞赛你迟早会和“最长回文子串”“回文子串计数”这类问题正面相遇。我见过不少同学把回文串题当成“玄学”靠肉眼观察对称、靠枚举所有子串去碰运气结果要么超时要么边界情况处理得头皮发麻。其实回文串的三大核心性质——对称扩展性、首尾递推子结构、回文半径覆盖——早就把回文串从“凭直觉认对称”变成了“可以计算、可以递推、可以优化的对称”。这篇内容想把这三条性质掰开揉碎讲清楚再配上 Python 里三种由浅入深的实现从最容易写对的中心扩展法到动态规划再到工程师面试里常用的 Manacher 算法。不管你现在是刚接触回文串还是想彻底弄懂线性算法背后的原理这篇内容都能给你一个可以直接落地的参考。1. 回文串的定义与判定边界1.1 什么样的字符串才算回文串回文串的定义一句话就能说完正着读和倒着读完全一样的字符串。比如 abba、racecar、level汉字里也有“上海自来水来自海上”这类经典例子。它本质上是一种轴对称结构轴的位置可能在某个字符上也可能在两个字符中间的空隙上。这个“轴”的两种存在形式直接决定了后面所有算法里“奇数长度和偶数长度要分别处理”的麻烦。你可能会觉得定义这么简单有什么好讲的真正写代码的时候麻烦事全在边界上。比如空字符串算不算回文按算法竞赛和 LeetCode 的惯例是算的因为空串正读反读都为空自然满足“相等”的条件。单个字符也算回文它正反都是自己。这两个边界如果没想清楚后面中心扩展法和动态规划里很多状态就不知道该不该初始化成 True。1.2 空串、单字符与奇偶长度的坑回文串长度的奇偶性是个绕不开的细节。奇数长度的回文串比如 abcba它的对称轴是一个具体的字符 c偶数长度的回文串比如 abba对称轴在 bb 中间的那条虚线上。许多初学者实现最长回文子串时只考虑了奇数情况结果遇到 abba 这种用例直接返回错误答案。这个问题还引出一个很重要的计数结论长度为 n 的字符串有 n 个字符中心和 n-1 个字符间隙中心总共 2n-1 个“回文中心”。后面要讲的中心扩展法就是围绕这 2n-1 个中心向外扩散的。如果你能把这个数字记牢写代码时就知道循环要从 0 跑到 2n-2或者直接用“左指针 i、右指针 i 与 i1”的写法把两种中心一起覆盖。1.3 判断单个字符串回文的基本姿势在展开核心性质之前先写写最基础的判断方法因为后面很多变体题都会复用这一套。判断一个字符串是不是回文串用双指针从两头往中间扫def is_palindrome(s: str) - bool: left, right 0, len(s) - 1 while left right: if s[left] ! s[right]: return False left 1 right - 1 return True这个函数的时间复杂度 O(n)空间复杂度 O(1)。它利用的就是“回文串首尾字符必须相等”这一条最直接的对称性质。只要有一次不相等就能立刻判定不是回文不需要再继续扫下去。这个双指针写法在“验证回文串”“回文链表”等问题里还会反复出现值得形成肌肉记忆。2. 三大核心性质拆解2.1 性质一中心对称与扩展性回文串最直观的性质是中心对称从它的对称中心向外看左边第 k 个字符一定等于右边第 k 个字符。反过来如果已知一个短回文串只要它左右两侧的字符相等那么把这两个字符分别拼到两边后得到的新字符串依然是一个回文串。这个扩展性是后面所有“以中心为起点找最长回文”算法的地基。想象一个向两边同步扩张的窗口初始时窗口就是中心本身长度 1或者中心两侧的空隙长度 0。不断比较左右两侧新进入窗口的字符如果相等就继续扩展直到不相等或越界为止。这时候窗口对应的字符串就是以这个中心为对称轴的最大回文串。这里有个很妙的点回文中心一共只有 2n-1 个所以你不需要去枚举 O(n^2) 个子串只需要枚举全部中心并对每个中心做扩展最坏情况下的比较次数也就是 O(n) 量级乘以中心数。这就是为什么中心扩展法虽然最坏时间复杂度是 O(n^2)但它实现简单、常数小在多数工程场景里反而表现很好。我用生活里的例子打个比方中心扩展就像照镜子镜子里你和镜子外你的动作总是对称的你往前走一步、镜子里的人也往前走一步。只要两侧“同步走”还能保持相同镜像就一直成立一旦有一侧已经走出边界或者内容对不上镜像就碎了。2.2 性质二首尾递推与子结构回文串的第二条核心性质是把回文和非回文用递归的方式联系起来一个子串 s[i..j] 是回文串当且仅当 s[i] s[j]并且去掉首尾后的子串 s[i1..j-1] 也是回文串。这里的边界条件是长度为 1 的子串一定是回文长度为 2 的子串只要两个字符相等就是回文。这条性质的价值在于它给了回文串一个清晰的“子结构”。判断长串回文之前不用重新扫一遍整个串只要查一下去掉首尾后的短串是不是回文就行。这就是动态规划能用来解回文串问题的根本原因大问题的最优解依赖于小问题的最优解并且小问题之间存在重叠可以缓存起来反复使用。举一个例子判断 abca 是否为回文首尾都是 a所以问题变成判断中间的 bc 是否为回文而 bc 首尾 b 和 c 不相等所以它不是回文于是 abca 也不是回文。整个过程只需要一次字符比较和一次查表非常快。我把这条性质单独拎出来强调是因为很多人做回文子串计数或最长回文子串时第一反应总是“枚举所有子串每个都调用一遍双指针判定””复杂度直接到了 O(n^3)。如果改用递推子结构就能用一张二维状态表记录所有子串的回文性把复杂度降到 O(n^2)。2.3 性质三回文半径与覆盖边界前两条性质能把回文串问题做到 O(n^2) 级别但第三条性质才是突破到 O(n) 的关键。这就是回文半径以及它的“镜像覆盖”特性。想象你已经找到了一个较长的回文串它的右边界是 right中心是 center。因为整个 [left, right] 范围内是完全对称的所以当你要计算对称中心右侧某个位置 i 的最大回文半径时可以先去左侧找它的镜像点 mirror。由于回文内部完全对称位置 i 的回文半径至少不会小于位置 mirror 的回文半径当然前提是它不能超出当前回文的右边界。这个“至少”并不是凭空猜出来的它是由回文内部的对称性严格保证的。Manacher 算法正是利用这一点在 O(n) 时间内跳过大量重复比较让每个位置只需借助已有的回文半径信息再加上极少量的实际字符比较就能确定自己的半径。换句话说每条“回文臂”最多被比较一次所以总体是线性的。后面到实现部分我会把这个过程走一遍你会发现代码很短但每一步都印证了这个性质。三个性质放在一张表里思路会清楚很多性质名称核心表述衍生算法时间复杂度中心对称扩展性回文中心最多 2n-1 个从中心向外扩展可得到最长回文中心扩展法O(n^2)首尾递推子结构s[i..j] 回文当且仅当首尾相等且内部回文动态规划O(n^2)回文半径覆盖右侧位置可从左侧镜像偷取初始半径且不超过右边界Manacher 算法O(n)这三条性质并不是互相排斥的它们是从不同角度描述同一件事。实际解决回文串题目时你可能同时用到性质一和性质二也可能故意用性质三追求更极致的性能。理解它们各自的适用场景比背模板代码重要得多。3. Python 实现从 O(n^2) 到 O(n)3.1 中心扩展法最容易写对的版本中心扩展法直接对应性质一。枚举所有可能的回文中心然后从这个中心向左右两边同时扩展记录扩展后的最大长度。def expand_around_center(s: str, left: int, right: int) - int: while left 0 and right len(s) and s[left] s[right]: left - 1 right 1 return right - left - 1 def longest_palindrome_expand(s: str) - str: if not s: return start, end 0, 0 for i in range(len(s)): # 奇数长度回文中心是 s[i] len1 expand_around_center(s, i, i) # 偶数长度回文中心在 s[i] 和 s[i1] 之间的空隙 len2 expand_around_center(s, i, i 1) max_len max(len1, len2) if max_len end - start: start i - (max_len - 1) // 2 end i max_len // 2 return s[start:end 1]为什么 expand_around_center 返回的是 right - left - 1因为循环结束时left 和 right 分别指向“第一个不满足相等条件”的左右位置真正的回文区间是 [left1, right-1]长度就是 right - left - 1。这段代码里最容易被忽略的是更新 start 和 end 时的索引计算。奇数长度回文和偶数长度回文的情况不同奇数长度时中心是字符串里的某个字符起始位置要向左偏移 (max_len - 1) // 2偶数长度时中心是两个字符之间的空隙结束位置是中心索引加上 max_len // 2。我一开始写的时候直接用 max_len // 2 去算两端结果奇数长度下总偏一位后来用 abcba 和 abba 两个用例手动推了一遍才想明白。提示中心扩展法天然适合“以某个中心向外扩散”的题目比如计算回文子串的数量。它的空间复杂度只有 O(1)这点比动态规划舒服很多。3.2 动态规划用状态表记录每个子串是否回文动态规划的思路对应性质二。我们开一张二维布尔表 dp其中 dp[i][j] 表示子串 s[i..j] 是否为回文。状态转移方程就是那两条递推关系长度为 1 恒为回文长度大于等于 2 时首尾相等并且内部子串回文。def longest_palindrome_dp(s: str) - str: n len(s) if n 2: return s dp [[False] * n for _ in range(n)] for i in range(n): dp[i][i] True start, max_len 0, 1 for length in range(2, n 1): for i in range(n - length 1): j i length - 1 if s[i] s[j]: if length 2 or dp[i 1][j - 1]: dp[i][j] True if length max_len: start, max_len i, length return s[start:start max_len]这里有几个实现细节值得单独说。遍历顺序必须按子串长度从小到大来而不是按左端点 i 的顺序。原因很直接要算 dp[i][j]你得先知道内部子串 dp[i1][j-1] 的结果而那个子串的长度比当前长度短。如果外层循环是 i内层循环是 j你在计算较长区间时内部的短区间可能还没被计算过查表就是错误的。初始化只设置了 dp[i][i] True那么长度为 2 的子串怎么处理它走的是 length 2 这个分支只要 s[i] s[j] 就直接置为 True不需要查内部因为内部根本不存在。这个分支条件如果不加dp[i1][j-1] 在 length 2 时会访问到未定义或者语义不对的位置非常容易出错。动态规划的优点是思路直观尤其适合变体题比如统计回文子串数量。缺点也明显二维表占了 O(n^2) 的空间n 到几千时还能扛n 上万内存就爆炸了。不过它的优化空间也很大因为 dp[i][j] 只依赖 dp[i1][j-1]也就是上一层的“ i1 行 j-1 列”理论上可以用滚动数组把空间压到 O(n)。实际刷题时如果不要求输出具体子串只要求“有多少个回文子串”可以只保存两个一维数组代码会更紧凑。3.3 Manacher 算法用回文半径覆盖实现线性时间要说回文串算法里的“天花板”还得是 Manacher。它的代码量比动态规划短运行时间是 O(n)但理解门槛也高。我建议先彻底搞懂性质三再来读这段代码。Manacher 的核心思路是先对原字符串做预处理在字符之间插入一个不会出现在原串中的分隔符比如 #。这样所有回文串都统一成了奇数长度偶数长度回文串的中心会落在这个分隔符上问题被简化成“只处理奇数回文半径”。def longest_palindrome_manacher(s: str) - str: if not s: return # 预处理统一奇偶长度 t [#] for ch in s: t.append(ch) t.append(#) n len(t) p [0] * n center, right 0, 0 for i in range(n): if i right: mirror 2 * center - i p[i] min(right - i, p[mirror]) # 中心扩展 while i - p[i] - 1 0 and i p[i] 1 n and t[i - p[i] - 1] t[i p[i] 1]: p[i] 1 # 更新 center 和 right if i p[i] right: center i right i p[i] max_len 0 center_idx 0 for i in range(n): if p[i] max_len: max_len p[i] center_idx i start (center_idx - max_len) // 2 return s[start:start max_len]我按运行顺序解释一下这段代码在干什么。预处理后的数组 t长度是 2n1。p[i] 记录的是以 t[i] 为中心、向两边扩展的“回文半径”注意这里的半径长度包括中心本身所以 p[i] 至少为 0也就是没有任何扩展。循环里先判断当前位置 i 是否落在当前维护的最右回文边界 right 之内。如果在那就找到它在当前回文内部的镜像位置 mirrorp[i] 可以直接初始化成一个非零值取值是 min(right - i, p[mirror])。这个 min 非常关键镜像位置的回文半径可能很大但当前位置不能超过当前回文的右边界否则超出部分无法被覆盖必须老老实实去字符比较。然后进入 while 循环它才是真正需要比较字符的地方。因为有了第一步的初始值这个 while 循环在很多位置上一开始就不满足条件直接跳过这就省下了大量比较。有些讲解把这一步称为“扩展剩余部分”我觉得很准确。更新 center 和 right 的时机是如果当前位置的回文右边界比之前的更靠右就把当前中心设为新的 center。也就是说Manacher 始终维护“能覆盖最右边界的那条回文臂”它是一切镜像快速初始化的保障。预处理后的串里分隔符 # 还有额外的好处p[i] 里恰好记录了对应原串中的回文半径长度。比如 t 中某个字符位置的回文半径是 k那么它在原串中对应的回文长度为 k。最终我们遍历一遍 p找到最大的半径和它的中心就能反推出最长回文子串在原串中的起点。这里还有一个容易踩到的细节start (center_idx - max_len) // 2 这个公式很多人不理解为什么直接整数除法就行。因为在预处理串里所有信息都被强制对齐到了“以字符为中心”的结构上中心索引减去半径正好对应原串回文起点的两倍索引关系所以除以 2 取整就是原起点。注意Manacher 的代码我建议不要只背而是每次运行前在心里走一遍 p 数组的生成过程。一个很好的验证方法是拿 abba 手算一遍。预处理串是 [#,a,#,b,#,b,#,a,#]中心是索引 4 的 #它的 p 值最终会扩展到 4对应原串回文长度正好是 4。你把这个过程推一遍比背十遍模板都有用。4. 实操中的坑与性能观察4.1 索引越界与奇偶长度的一线之隔回文串算法里的错误十有八九出在索引边界上。中心扩展法会忘掉偶数中心动态规划会忘记 length 2 的特殊分支Manacher 会在 while 循环里少写一个越界判断。我把这些高频错误整理成了一张速查表场景典型错误正确处理中心扩展只调用 expand(s, i, i)漏掉 i 和 i1 的偶数中心两个方向都要试中心扩展更新 start/end 时奇偶公式混用奇数用 (max_len-1)//2偶数用 max_len//2动态规划遍历顺序按 i 从小到大导致内部子串状态未计算外层按子串长度从小到大遍历动态规划length 2 时查 dp[i1][j-1]长度 2 单独处理直接比较两端Manacherwhile 循环里没有检查 i-p[i]-1 和 ip[i]1 的边界两个边界条件必须写全Manacher忘记预处理后返回区间和原串下标的映射关系用 (center_idx - max_len) // 2 换算起点排查这些问题的通用方法我个人强烈推荐一种构造一个长度很短的字符串比如 a、aa、aba、abba、abcba全部跑一遍然后手动打印出每个中心/每个状态的中间值。回文串算法的调试最怕就是只看最终答案。因为最长回文子串偶尔会歪打正着返回正确结果但计数变体题立马就会暴露问题。把中间输出打出来的习惯能帮你省下至少一半的 Debug 时间。4.2 三种实现的实测表现怎么理解虽然从复杂度上看Manacher 的 O(n) 碾压中心扩展和动态规划的 O(n^2)但实际跑起来并没有那么绝对。用随机生成的小写字母字符串做对比在 n 1000 时中心扩展法因为常数小、操作简单速度可能比动态规划还快。动态规划因为要初始化整个二维表内存访问密集反而显得更慢。Manacher 在这个规模下优势不明显代码里还有预处理和数组访问的额外开销。n 到 5000 以上时差距开始拉开。中心扩展大致是几十毫秒到百毫秒级别动态规划随内存区域扩大越来越吃力Manacher 依然是十几毫秒到几十毫秒级别。n 到 10000 甚至更大时复杂度差异已经不可忽略了。具体数字随机器和 Python 解释器版本浮动建议不要只看绝对数值而是记住趋势输入规模越大O(n) 的优势越明显。我的经验是在笔试和面试场景里如果 n 不超过几千直接写中心扩展法或动态规划完全够用代码短、不容易错面试官也好理解。只有当 n 上到几十万或者题目要求你在 O(n) 时间内解决时才需要上 Manacher。盲目追求最优算法反而容易在边界条件上翻车。4.3 回文串变体题目怎么用这三条性质理解了三大核心性质之后回文串题目的“套路感”会强很多。我把常见的变体题和它们对应的性质列一下方便你刷题时对号入座。回文子串数量统计用中心扩展法最舒服从每个中心向外数一下有多少个能扩展成功的回文加起来就是答案。动态规划也可以做但空间占用大一些。分割回文串问题也就是把一个字符串切成若干段每段都是回文。这类题几乎必用性质二来预处理所有子串是否回文然后再做深搜回溯或动态规划。预处理阶段就是在填那张二维布尔表。最长回文子序列问题注意它不要求连续所以不能用“回文半径”或“中心扩展”的思路。它本质上是动态规划状态转移来自“首尾字符相等与否”的决策可以看成性质二在非连续场景下的推广。很多刷题的人在这个地方栽跟头是因为把“子串”和“子序列”混为一谈上来就枚举中心结果自然不对。把字符串变成回文最少需要插入几次字符这类题通常转化成“原串与反转串的最长公共子序列长度”核心也不是回文算法本身但它背后的对称观念和性质二的重叠子问题思想是相通的。如果题目要求一个字符串里的最长回文前缀或回文后缀Manacher 的预处理方案会很方便因为处理后的 p 数组可以直接告诉你从开头开始最长的回文有多长不需要再单独做 KMP 或者哈希。把这些变体题放在一起看你会发现掌握了三大性质本质上就是掌握了一套“从不同角度利用对称性”的思维方式。刷题时先冷静判断这题要求连续子串还是子序列最长一个还是所有输出答案还是只计数选对性质再选算法思路就顺了。5. 收尾前再分享一点个人体会我在刚开始刷回文串问题时最大的误区就是总想一次性写出最优解。后来踩过几次坑调整成一条很简单的策略先确认边界要求再选择算法。凡是 n 不大或者只要求返回一个结果的题我优先写中心扩展法因为它的正确性最好验证凡是要求计数且 n 中等动态规划写起来更快只有当题目明确卡了 O(n) 复杂度或者数据范围大到 O(n^2) 完全跑不过去时才掏出 Manacher。这套取舍在面试和实际工程里都适用因为代码的可读性和可维护性很多时候比常数优化更重要。最后分享一个小技巧如果你经常记混预处理后的索引映射可以在 Manacher 实现里多加一个辅助函数把预处理串的索引和原串索引互转的逻辑封装起来比如 idx (i - 1) // 2。这样主逻辑只管半径计算回文起点的换算交给专门的函数处理出错概率会小很多。这个习惯后来帮我解决了不少回文串变体题的调试时间。