Manacher算法深度解析用Python和Java征服面试中的回文难题回文串判断是算法面试中的经典问题而Manacher算法则是解决最长回文子串问题的终极武器。本文将带你从零开始彻底掌握这个让无数面试者又爱又怕的高效算法。1. 为什么需要Manacher算法在字符串处理领域回文问题一直占据着重要地位。传统解决方案如暴力搜索法时间复杂度高达O(n³)而改进后的中心扩展算法也只能达到O(n²)。当面对海量文本处理时这些方法显得力不从心。Manacher算法的三大优势线性时间复杂度O(n)处理百万级字符串游刃有余空间复杂度O(n)仅需额外存储回文半径数组统一处理奇偶长度回文逻辑简洁优雅实际应用场景包括DNA序列分析文本相似度计算恶意代码特征检测数据压缩与加密提示大厂面试中面试官通常会要求比较不同算法的优劣因此理解Manacher的优化原理比记忆代码更重要。2. 中心扩展算法Manacher的前身理解Manacher算法前必须先掌握中心扩展算法这是Manacher的思想基础。2.1 算法核心思想中心扩展算法遍历字符串的每个位置将其视为回文中心向两侧扩展def expand_around_center(s, left, right): while left 0 and right len(s) and s[left] s[right]: left - 1 right 1 return (right - left - 1) // 2 # 返回回文半径关键点奇数长度回文中心为单个字符偶数长度回文中心为两个相同字符需要处理两种中心情况2.2 复杂度分析操作时间复杂度空间复杂度遍历所有中心点O(n)O(1)每个中心扩展O(n)-总计O(n²)O(1)虽然比暴力法进步但O(n²)复杂度在大数据场景下仍不够理想。3. Manacher算法的精妙设计3.1 预处理统一奇偶处理Manacher算法的第一步是通过插入特殊字符如#将字符串长度变为奇数原始字符串 abba 预处理后 #a#b#b#a#这种转换带来两个好处无需区分奇偶情况回文半径与原字符串长度直接对应Java实现示例private String preprocess(String s) { StringBuilder sb new StringBuilder(); sb.append(#); for (char c : s.toCharArray()) { sb.append(c).append(#); } return sb.toString(); }3.2 核心概念与变量关键变量pArr[]存储每个位置的回文半径C当前最右回文串的中心R当前最右回文串的右边界镜像原理 对于位置i其关于中心C的镜像位置i满足i 2 * C - i利用这一性质可以避免重复计算是算法达到线性的关键。3.3 四种情况处理Manacher算法在处理每个位置时分为四种情况i在R外朴素中心扩展i的回文在L-R内直接复制镜像值i的回文超出L半径至少为R-ii的回文刚好压线需要继续扩展Python实现核心逻辑def manacher(s): T #.join(^{}$.format(s)) n len(T) P [0] * n C R 0 for i in range(1, n-1): # 关键镜像计算 mirror 2*C - i if R i: P[i] min(R-i, P[mirror]) # 尝试扩展 while T[i P[i] 1] T[i - P[i] - 1]: P[i] 1 # 更新中心和右边界 if i P[i] R: C, R i, i P[i] max_len, center max((n, i) for i, n in enumerate(P)) return s[(center - max_len)//2 : (center max_len)//2]4. 复杂度分析与面试技巧4.1 时间复杂度证明Manacher算法的时间复杂度为O(n)这是因为每个位置i的扩展操作要么从R开始要么只进行一步比较R在整个过程中单调递增因此总比较次数不超过2n次。4.2 面试常见问题Q1为什么预处理要加特殊字符统一奇偶处理避免边界条件判断方便计算原字符串位置Q2如何从pArr恢复最长回文子串int maxLen 0; int center 0; for (int i 0; i pArr.length; i) { if (pArr[i] maxLen) { maxLen pArr[i]; center i; } } int start (center - maxLen) / 2; return s.substring(start, start maxLen);Q3算法中的R和C如何更新当i pArr[i] R时更新C总是取当前最右回文的中心R C pArr[C]5. 双语言完整实现5.1 Python实现def longest_palindrome(s): if not s: return # 预处理 T #.join(^{}$.format(s)) n len(T) P [0] * n C R 0 for i in range(1, n-1): # 利用镜像加速 mirror 2*C - i if i R: P[i] min(R-i, P[mirror]) # 中心扩展 while T[i P[i] 1] T[i - P[i] - 1]: P[i] 1 # 更新最右回文 if i P[i] R: C, R i, i P[i] # 提取结果 max_len, center max((n, i) for i, n in enumerate(P)) return s[(center - max_len)//2 : (center max_len)//2]5.2 Java实现public String longestPalindrome(String s) { if (s null || s.length() 0) return ; char[] T preprocess(s).toCharArray(); int n T.length; int[] P new int[n]; int C 0, R 0; for (int i 1; i n-1; i) { int mirror 2*C - i; if (i R) { P[i] Math.min(R - i, P[mirror]); } while (T[i P[i] 1] T[i - P[i] - 1]) { P[i]; } if (i P[i] R) { C i; R i P[i]; } } int maxLen 0; int center 0; for (int i 0; i n; i) { if (P[i] maxLen) { maxLen P[i]; center i; } } int start (center - maxLen) / 2; return s.substring(start, start maxLen); } private String preprocess(String s) { StringBuilder sb new StringBuilder(); sb.append(^); for (char c : s.toCharArray()) { sb.append(#).append(c); } sb.append(#$); return sb.toString(); }6. 实战优化与边界处理在实际编码面试中还需要注意以下细节边界条件处理空字符串输入全相同字符单字符输入代码优化技巧预处理时添加边界字符(^和$)避免越界检查使用数组而非List提高访问速度合并某些判断条件调试技巧# 调试打印 print(fi{i}, C{C}, R{R}, P{P}) # 可视化当前状态 print(T) print(.join(str(p) if p 0 else . for p in P))7. 扩展应用与变种问题掌握了基础算法后可以解决一系列变种问题统计所有回文子串数量对pArr求和后转换公式count sum((p 1) // 2 for p in pArr)最长回文前缀/后缀在算法运行过程中监控特定边界提前终止条件优化回文分割问题结合动态规划使用Manacher预处理回文信息多字符串回文匹配扩展预处理方式处理特殊分隔符在准备算法面试时建议将Manacher算法与以下知识点结合复习KMP算法字符串匹配动态规划回文分割滑动窗口回文子串统计Trie树回文对问题