从暴力到Manacher：最长回文子串算法优化全记录（含复杂度分析）

从暴力到Manacher最长回文子串算法优化全记录含复杂度分析回文串作为字符串处理中的经典问题在算法竞赛和实际工程中都有广泛应用。从最直观的暴力解法到精巧的Manacher算法不同时间复杂度的解决方案展现了算法设计的艺术。本文将系统梳理五种主流解法通过复杂度对比、核心思路图解和实战代码解析帮助读者掌握算法优化的方法论。1. 暴力枚举法O(n³)的起点暴力法直接枚举所有可能的子串再逐一验证是否为回文。具体步骤如下双重循环枚举子串外层循环确定起始位置i内层循环确定结束位置ji ≤ j验证回文性对每个子串s[i...j]检查s[ik] s[j-k]是否对所有k成立def longest_palindrome_brute_force(s): n len(s) max_len 1 for i in range(n): for j in range(i, n): if s[i:j1] s[i:j1][::-1]: max_len max(max_len, j-i1) return max_len复杂度分析时间复杂度O(n³)两层循环O(n²) × 回文验证O(n)空间复杂度O(1)提示虽然暴力法效率低下但作为基准方案它能帮助我们理解问题本质并验证其他算法的正确性。2. 中点扩散法利用对称性降为O(n²)观察到回文串的对称特性可以枚举每个可能的中心点向两侧扩展直到不匹配中心类型初始边界示例奇数长度lriaba偶数长度li, ri1abbaint expandAroundCenter(const string s, int l, int r) { while (l 0 r s.size() s[l] s[r]) { l--; r; } return r - l - 1; } int longestPalindrome(string s) { int res 0; for (int i 0; i s.size(); i) { int len1 expandAroundCenter(s, i, i); // 奇数情况 int len2 expandAroundCenter(s, i, i1); // 偶数情况 res max(res, max(len1, len2)); } return res; }优化效果时间复杂度降至O(n²)空间复杂度保持O(1)3. 动态规划空间换时间的O(n²)方案建立状态转移表利用已计算的子问题结果优化性能状态定义dp[i][j]表示子串s[i...j]是否为回文转移方程dp[i][j] (s[i] s[j]) (j-i 3 || dp[i1][j-1])关键实现技巧按子串长度从小到大处理边界条件单个字符必为回文def dp_solution(s): n len(s) dp [[False]*n for _ in range(n)] max_len 1 for i in range(n): dp[i][i] True for l in range(2, n1): # 子串长度 for i in range(n-l1): j i l - 1 if s[i] s[j]: if l 2 or dp[i1][j-1]: dp[i][j] True max_len max(max_len, l) return max_len性能对比与中点扩散法同为O(n²)更适合需要多次查询的场景预处理后查询O(1)4. 哈希二分O(nlogn)的折中方案结合字符串哈希的快速比较与二分的查找效率实现步骤预处理正向和反向哈希数组对每个字符作为中心二分查找最大回文半径通过哈希值比较验证回文性typedef unsigned long long ULL; const int P 131; ULL getHash(ULL h[], ULL p[], int l, int r) { return h[r] - h[l-1] * p[r-l1]; } int solve(string s) { int n s.size(); ULL hl[n2], hr[n2], p[n2]; p[0] 1; // 预处理哈希 for (int i 1; i n; i) { hl[i] hl[i-1] * P s[i-1]; hr[i] hr[i-1] * P s[n-i]; p[i] p[i-1] * P; } int res 0; for (int i 1; i n; i) { // 二分查找奇数长度 int l 0, r min(i-1, n-i); while (l r) { int mid (l r 1) 1; if (getHash(hl, p, i-mid, i-1) getHash(hr, p, n-(imid)1, n-(i1)1)) { l mid; } else { r mid - 1; } } res max(res, 2*l 1); // 二分查找偶数长度略 } return res; }适用场景字符串长度较大1e5级别需要比O(n²)更优的解决方案5. Manacher算法O(n)的终极优化Manacher算法通过巧妙的预处理和对称性利用将时间复杂度降至线性核心技巧统一奇偶情况插入特殊字符如#维护当前最右回文边界R和中心点C利用对称性减少重复计算def manacher(s): T #.join(^{}$.format(s)) n len(T) P [0] * n C R 0 for i in range(1, n-1): if i R: P[i] min(R-i, P[2*C - i]) 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 max(P) return max_len算法精要镜像加速当i在当前最右边界R内时直接利用对称点结果中心扩展无法利用镜像时进行常规中心扩展边界更新发现更右的回文时更新R和C复杂度对比表算法时间复杂度空间复杂度适用场景暴力枚举O(n³)O(1)小规模数据验证中点扩散O(n²)O(1)中等规模实现简单动态规划O(n²)O(n²)需要多次查询哈希二分O(nlogn)O(n)大规模数据ManacherO(n)O(n)超大规模数据实际项目中在LeetCode等平台处理1e3量级数据时中点扩散法因其实现简单往往更受青睐而当面对1e6以上规模时Manacher的线性优势将无可替代。我曾在一个文本分析项目中处理百万级DNA序列将Manacher算法与多线程结合性能较动态规划提升约40倍。