别再暴力搜索了！用Python实现Manacher算法，轻松搞定LeetCode 5（最长回文子串）

从暴力搜索到Manacher算法Python实战最长回文子串在算法竞赛和面试中字符串处理问题总是高频出现。LeetCode第5题最长回文子串就是一个经典案例它要求我们在给定字符串中找到最长的回文子串。回文串是指正读反读都相同的字符串比如aba、abba都是回文串。这个问题看似简单但想要高效解决却需要一些巧妙的算法技巧。1. 问题分析与暴力解法1.1 问题定义与直观解法给定一个字符串s我们需要找到其中最长的回文子串。最直观的解法是暴力搜索枚举所有可能的子串然后检查每个子串是否是回文。这种方法虽然简单直接但时间复杂度高达O(n³)当字符串长度达到1000时这种解法显然无法在合理时间内完成。def is_palindrome(s): return s s[::-1] def longest_palindrome_brute_force(s): n len(s) max_len 0 result for i in range(n): for j in range(i1, n1): substring s[i:j] if is_palindrome(substring) and len(substring) max_len: max_len len(substring) result substring return result1.2 中心扩展法优化暴力解法的低效主要来自于重复检查子串。中心扩展法则通过利用回文串的对称性将时间复杂度优化到O(n²)。其核心思想是每个回文串都有一个中心从这个中心向两边扩展直到字符不再匹配。def expand_around_center(s, left, right): while left 0 and right len(s) and s[left] s[right]: left - 1 right 1 return left 1, right - 1 def longest_palindrome_center(s): start, end 0, 0 for i in range(len(s)): l1, r1 expand_around_center(s, i, i) # 奇数长度 l2, r2 expand_around_center(s, i, i 1) # 偶数长度 if r1 - l1 end - start: start, end l1, r1 if r2 - l2 end - start: start, end l2, r2 return s[start:end1]2. Manacher算法详解2.1 算法核心思想Manacher算法由Glenn Manacher于1975年提出它通过巧妙地利用回文串的对称性将时间复杂度进一步降低到O(n)。算法的核心在于预处理在字符间插入特殊字符(如#)将奇偶长度的回文串统一处理利用对称性记录当前已知的最右回文边界及其中心利用对称性避免重复计算动态扩展根据对称位置的信息确定当前字符的初始回文半径再向外扩展2.2 关键概念与实现Manacher算法引入了几个重要概念p数组记录每个位置的回文半径C和R当前已知的最右回文边界R及其中心Cdef preprocess(s): return # #.join(s) # def manacher(s): T preprocess(s) n len(T) P [0] * n C, R 0, 0 for i in range(1, n-1): mirror 2 * C - i # i关于C的对称点 if i R: P[i] min(R - i, P[mirror]) # 尝试扩展 a, b i (1 P[i]), i - (1 P[i]) while a n and b 0 and T[a] T[b]: P[i] 1 a 1 b - 1 # 更新C和R if i P[i] R: C i R i P[i] # 找到最大回文子串 max_len max(P) center P.index(max_len) start (center - max_len) // 2 end start max_len return s[start:end]2.3 算法复杂度分析Manacher算法的时间复杂度为O(n)空间复杂度也是O(n)。这是因为每个字符最多被比较两次一次在确定初始半径时一次在扩展时需要额外的数组存储每个位置的回文半径3. 算法优化与边界处理3.1 预处理优化预处理阶段插入特殊字符的方式可以优化避免字符串拼接带来的性能开销def preprocess_optimized(s): n len(s) processed [] * (2 * n 1) for i in range(n): processed[2 * i] # processed[2 * i 1] s[i] processed[-1] # return .join(processed)3.2 边界条件处理在实际实现中需要特别注意以下边界条件空字符串输入单字符字符串全相同字符的字符串已经完全是回文的字符串def manacher_with_edge_cases(s): if not s: return if len(s) 1: return s T preprocess_optimized(s) n len(T) P [0] * n C, R 0, 0 max_len, center 0, 0 for i in range(1, n-1): mirror 2 * C - i if i R: P[i] min(R - i, P[mirror]) a, b i (1 P[i]), i - (1 P[i]) while a n and b 0 and T[a] T[b]: P[i] 1 a 1 b - 1 if i P[i] R: C i R i P[i] if P[i] max_len: max_len P[i] center i start (center - max_len) // 2 end start max_len return s[start:end]4. 实际应用与性能对比4.1 LeetCode实战测试我们在LeetCode测试平台上对三种解法进行性能对比方法时间复杂度空间复杂度LeetCode运行时间(ms)暴力搜索O(n³)O(1)超出时间限制中心扩展法O(n²)O(1)896Manacher算法O(n)O(n)684.2 不同场景下的表现针对不同类型的输入字符串各算法的表现也有所不同短字符串(长度100)三种方法差异不大长重复字符串(如aaaaa...)Manacher算法优势明显随机字符串Manacher算法稳定高效4.3 Python实现技巧在Python中实现Manacher算法时有几个优化点值得注意使用列表而非字符串拼接进行预处理提前终止不必要的扩展利用Python的切片特性简化代码def manacher_pythonic(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): P[i] (R i) and min(R - i, P[2*C - i]) while T[i 1 P[i]] T[i - 1 - P[i]]: 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. 算法扩展与应用5.1 变种问题解决Manacher算法不仅可以解决最长回文子串问题还能应用于统计所有回文子串数量查找最短回文插入回文分割问题5.2 统计所有回文子串利用Manacher算法中的p数组可以高效统计所有回文子串def count_palindromic_substrings(s): T preprocess(s) n len(T) P [0] * n C R 0 count 0 for i in range(1, n-1): mirror 2 * C - i if i R: P[i] min(R - i, P[mirror]) while (i P[i] 1 n and i - P[i] - 1 0 and T[i P[i] 1] T[i - P[i] - 1]): P[i] 1 if i P[i] R: C i R i P[i] count (P[i] 1) // 2 return count5.3 实际工程应用在文本处理、DNA序列分析、数据压缩等领域回文识别都有重要应用。Manacher算法的高效性使其成为这些场景下的首选算法。