先把定位说清楚免得你白紧张Manacher是面试加分项不是常规要求。绝大多数面试里答出“中心扩散O(n²)”就已经过关了但如果你能在白板上把Manacher讲明白那是实打实的亮点。更值得你带走的是Manacher背后的思想——它和KMP是同一条脉络已经算出来的信息绝不再算第二遍。KMP靠“最长相等前后缀”让主串指针不回退Manacher靠“回文的对称性”让扩散半径不从头开始。两者都是用一份预处理信息把重复劳动一次性省掉。 题目速览 LeetCode 530秒读懂给你一个字符串s找到s中最长的回文子串。示例babad→bababa也合法示例cbbd→bb示例a→a约束n ≤ 1000仅数字和英文字母。“回文”就是正读反读都一样aba是abba也是。注意前者长度是奇数中心是单个字符b后者是偶数中心是bb之间的空隙——奇偶中心不同是所有回文解法的第一个绊脚石。 核心思路从暴力到Manacher的进化链① 暴力枚举枚举所有子串O(n²)个每个判回文O(n) →O(n³)。② 动态规划dp[i][j]表示s[i..j]是否回文转移dp[i][j] dp[i1][j-1] s[i]s[j]→O(n²)时间 O(n²)空间。③ 中心扩散枚举每个可能的中心n个奇数中心 n-1个偶数中心各向两边扩散 →O(n²)时间、O(1)空间。这是“够用解”。④ Manacher中心扩散的瓶颈在于——每个中心的半径都从0开始重新数。回文有对称性如果我已知一个以C为中心、右边界到R的大回文那么对于C右侧的某个位置i它关于C的镜像点mirror 2C - i的半径已经被算过了可以直接拿来当i的初始半径。Manacher的三个组件预处理在字符间插入分隔符如#把奇偶长度统一成奇数——aba变#a#b#a#abba变#a#b#b#a#维护最右边界记录当前已探明的、右边界最靠右的那个回文的中心center与右边界right镜像复用若i right则p[i]的初始值可以取min(right - i, p[mirror])不必从1开始扩散那个min里的两个含义要分清p[mirror]是镜像点的半径能复用多少right - i是“别超出已知大回文的边界”超出部分未经验证不能用。一句话核心用分隔符统一奇偶 → 用最右边界记住“探明区域” → 用镜像把新位置的半径初始化从而让扩散总量变成线性。️ 图解算法手把手走一遍以s abba为例。预处理后t #a#b#b#a#长度n 9下标012345678字符#a#b#b#a#逐位推进p[i]为以i为中心的回文半径含中心right为最右已探明边界it[i]在边界内?镜像点p[mirror]初始p[i]扩散后p[i]更新后 (center, right)0#否——11(0, 1)1a否——12(1, 3)2#是(23)01min(1,1)11(1, 3)3b否(33)——12(3, 5)4#是(45)21min(1,1)15(4, 9)5b是32min(4,2)22(4, 9)6#是21min(3,1)11(4, 9)7a是12min(2,2)22(4, 9)8#是01min(1,1)11(4, 9)关键看i 4它落在已知回文center3, right5内镜像点mirror 2×3-4 2p[2] 1于是初始半径直接给到1。随后扩散一路匹配到p[4] 5覆盖了t[0..8]对应原串abba——中心回文被一次性发现。还原答案p[i]是在t中的半径转回原串有固定公式起始下标start (i - p[i] 1) / 2 原串长度len p[i] - 1i4 时start (4-51)/2 0len 5-1 4→s[0:4] abba✓ 代码实现Python JavaPython版classSolution:# ---------- 够用解中心扩散O(n²) / O(1) ----------deflongestPalindrome_expand(self,s:str)-str:nlen(s)ifn2:returns start,max_len0,1foriinrange(n):# 奇数长度回文中心是单个字符l,ri,iwhilel0andrnands[l]s[r]:l-1r1ifr-l-1max_len:# 越界后r-l-1才是真实长度max_len,startr-l-1,l1# 偶数长度回文中心是两个字符之间l,ri,i1whilel0andrnands[l]s[r]:l-1r1ifr-l-1max_len:max_len,startr-l-1,l1returns[start:startmax_len]# ---------- 最优解ManacherO(n) ----------deflongestPalindrome(self,s:str)-str:ifnots:returnt##.join(s)## 插入分隔符统一奇偶nlen(t)p[1]*n# p[i]半径含中心centerright0# 最右回文的中心与右边界best_i0foriinrange(n):ifiright:# 在已知边界内 → 镜像复用mirror2*center-i p[i]min(right-i,p[mirror])while(i-p[i]0andip[i]nandt[i-p[i]]t[ip[i]]):p[i]1# 从已有半径继续扩散ifip[i]right:# 刷新最右边界center,righti,ip[i]ifp[i]p[best_i]:best_ii start(best_i-p[best_i]1)//2returns[start:startp[best_i]-1]Java版classSolution{publicStringlongestPalindrome(Strings){if(snull||s.length()0)return;StringBuildersbnewStringBuilder(#);for(charc:s.toCharArray())sb.append(c).append(#);Stringtsb.toString();intnt.length();int[]pnewint[n];for(inti0;in;i)p[i]1;intcenter0,right0;intbestI0;for(inti0;in;i){if(iright){intmirror2*center-i;p[i]Math.min(right-i,p[mirror]);}while(i-p[i]0ip[i]nt.charAt(i-p[i])t.charAt(ip[i])){p[i];}if(ip[i]right){centeri;rightip[i];}if(p[i]p[bestI])bestIi;}intstart(bestI-p[bestI]1)/2;returns.substring(start,startp[bestI]-1);}}⚠️防坑提醒必看p的初值必须是1中心自身就是一个长度为1的回文不是0。min(right - i, p[mirror])里的right - i不能省——它保证初始半径不越过“已探明区域”。转回原串的公式start (i - p[i] 1) // 2len p[i] - 1。⏱️ 复杂度分析面试必问时间O(n)这是Manacher最反直觉的地方——明明有内层while循环为什么是线性因为每当扩散成功一次right就至少右移一格而right最多右移n次加上镜像复用时直接跳过扩散总扩散次数被摊还成O(n)。这属于摊还分析的结论和双栈队列的均摊O(1)是同一类思想。空间O(n)p数组 预处理串t。解法时间空间暴力枚举O(n³)O(1)区间DPO(n²)O(n²)中心扩散O(n²)O(1)ManacherO(n)O(n)实测O(n)的保证值多少钱串长4000CPython 3.13输入最长回文长度Manacher中心扩散结论随机ab串260.0027s0.0018s中心扩散快1.5×a/b/aa混合400.0036s0.0031s中心扩散略快全a回文极长40000.0023s0.7293sManacher快314倍随机串上Manacher反而慢——因为回文平均长度只有26中心扩散接近O(n)而Manacher要先构造2n1的分隔串、再走2n1个中心预处理常数白白付了出去。但回文一旦变长中心扩散立刻崩全a时它是实打实的O(n²)每个中心都要扩2000次耗时从0.0018s涨到0.7293s涨了400倍而Manacher因为镜像复用耗时反而略微下降。这就是理论保证的价值中心扩散的性能取决于数据Manacher的性能不取决于数据。生产环境的输入往往不是随机的——文本里可能出现aaaa...aaa、回文结构密集的HTML/XML片段、或用户恶意构造的退化输入。买Manacher买的不是“平均更快”而是“任何输入都不会退化”。 隐藏价值p数组还能一行统计回文子串数LC.647p[i]不只是“半径”它直接等于以t[i]为中心、在原串里的回文子串个数defcountSubstrings(s:str)-int:t##.join(s)#nlen(t)p[1]*n centerright0foriinrange(n):ifiright:mirror2*center-i p[i]min(right-i,p[mirror])whilei-p[i]0andip[i]nandt[i-p[i]]t[ip[i]]:p[i]1ifip[i]right:center,righti,ip[i]returnsum(x//2forxinp)# 每个中心贡献 p[i]//2 个回文公式是sum(p[i] // 2)逐个整除再求和不能写成sum(p) // 2先求和再除会多算因为每个中心的取整损失被累积放大了。用s aaa核一遍t #a#a#a#跑出p [1, 2, 3, 4, 3, 2, 1]逐个整除求和0112110 6而暴力枚举aaa的回文子串是a×3 aa×2 aaa×1 6 ✓若误写成sum(p) // 2会得到8错在两个半截回文被凑成了一整个。这是Manacher的隐藏价值跑完一遍p数组整串的回文结构信息就全在里面了。 举一反三5道高频变体题题号题目与本题的关系LC.647回文子串计数p数组直接求和见上LC.516最长回文子序列注意是子序列用区间DPManacher不适用LC.214最短回文串KMP的应用与 Manacher不同路LC.131分割回文串回文判定 回溯LC.5最长回文子串本题 面试追问模拟提前准备惊艳全场Q1为什么p[i]要取min(right - i, p[mirror])两个上界含义不同p[mirror]是“镜像点能复用多少半径”right - i是“不能超过已探明区域的右边界”。只有p[mirror]完全落在边界内时才完全复用一旦超出超出的部分没有对称性保证必须老实扩散。Q2预处理插入#的作用是啥统一奇偶。奇回文如aba中心是字符偶回文如abba中心是空隙插入分隔符后两种回文在t中都变成“以某个字符为中心的奇回文”代码只需处理一种情况。Q3Manacher和KMP有什么共通之处都是“已算过的信息不再重算”KMP用next数组记住最长前后缀失配时模式串滑到该位置Manacher用p数组记住半径新位置从镜像半径起步。两者都把O(n²)或更差的重复劳动压到O(n)。Q4工程里用得多吗不算高频。但它出现在一些特定领域生物信息学的回文序列检测、文本处理的对称结构分析。面试中的价值主要是展示你对摊还分析和对称性利用的理解深度。 实战小技巧刷题党必备口诀插分隔符统奇偶最右边界记探明镜像复用省扩散。模板Manacher 预处理 最右边界 镜像复用 扩散。防坑p初值必须为1right - i不能省还原公式别记错。 实际应用场景不止是刷题生物信息学DNA回文序列识别限制性内切酶切点文本处理对称结构分析数据压缩对称模式检测 今日思考题Manacher的p数组其实还能直接算出“字符串里一共有多少个回文子串”LC.647。提示p[i]是半径半径内的每一层都是一个回文。你能想到怎么从p[i]推出以i为中心的回文子串个数吗