马拉车算法是一种能够在线性时间内查找一个字符串的所有回文子串的算法。它主要应用于与回文相关的问题尤其适用于需要快速处理的场景。该算法通常用于解决最长回文子串在 O(n) 时间内找到最长的连续回文子串。多次回文查询经过 O(n) 时间预处理后可在 O(1) 时间内回答诸如 “子串 s[i..j] 是否为回文” 的问题。暴力法或动态规划等传统方法的时间复杂度为 O(n²)而拉宾 - 卡普算法滚动哈希需 O(n × log n) 时间这些方法在处理长字符串或多次查询时效率较低。马拉车算法能以 O(n) 时间高效解决这些问题。一、为什么暴力法、动态规划、中心扩展法或哈希法效率不够高在深入讲解马拉车算法之前我们先简要分析处理回文问题的常用方法及其效率短板。1、暴力法枚举所有可能的子串通过逐字符比较判断是否为回文。子串总数为 O(n²)每个子串的判断最多耗时 O(n)。时间复杂度O(n³)缺点即使输入规模中等速度也非常慢。2、动态规划DP使用二维表dp[i][j]存储 s[i..j] 是否为回文。利用已计算的结果填充表格。时间复杂度O(n²)空间复杂度O(n²)缺点对于长字符串而言速度依然过慢且空间开销大。3、中心扩展法将每个字符和字符间的空隙当作潜在的回文中心。对每个中心不断向左右扩展只要 s[left]s[right] 就继续。记录扩展过程中找到的最长回文。时间复杂度O(n²)空间复杂度O(1)缺点最坏情况下时间复杂度仍是平方级对于长字符串效率不如马拉车算法。4、拉宾 - 卡普哈希 二分查找使用滚动哈希比较子串与它的反转串。结合二分查找找到以每个位置为中心的最长回文。时间复杂度O(n × log n)因对每个中心进行二分查找。空间复杂度O(n)存储前缀哈希。缺点虽比动态规划快得多但仍非最优且需注意避免哈希冲突。5、马拉车算法的优势以上所有方法的速度都慢于线性时间。马拉车算法基于对称性和中心扩展的巧妙思想以线性时间O(n)解决相同问题不计结果数组空间开销为常数。二、字符串预处理1、为什么需要预处理在普通字符串中回文子串有奇数和偶数两种长度奇数长度aba、racecar偶数长度abba、noon分开处理这两种情况会让实现变得复杂。为简化逻辑、统一处理所有回文马拉车算法会修改原字符串使得所有回文都变为奇数长度。每个字符和字符间的空隙都可作为回文中心。这避免了为奇偶长度分别编写代码实现了统一的扩展逻辑。2、代码实现方式① 以开头作为左边界哨兵避免扩展时越界检查。② 在字符之间插入#保证原字符相互分隔。偶数长度回文如abba会变为#a#b#b#a#。奇偶情况在转换后的字符串中统一为奇数长度。③ 以$结尾作为右边界哨兵安全处理边界。示例输入字符串s abba转换后字符串ms #a#b#b#a#$现在每个字符包括#都可作为回文的潜在中心。这种转换简化了算法核心逻辑保证行为一致。三、算法核心预处理后算法对转换后的字符串ms进行单次遍历计算数组p[]p[i]存储以位置i为中心的最长回文的半径单侧字符数。该逻辑在runManacher()函数中实现。1、关键变量int l 0, r 0;l和r表示当前找到的最右侧回文的左右边界。2、遍历转换后的字符串从索引 1 开始索引 0 是哨兵。在 n−1 处结束索引 n−1 是哨兵$。3、镜像优化p[i] max(0, min(r - i, p[r l - i]));如果 i 在当前回文区间 [l,r] 内利用 i 关于中心的镜像点初始化p[i]。镜像位置mirror l r - i取p[mirror]和剩余范围r - i中的较小值防止越界。这避免了重复计算是算法达到线性时间的核心。4、以 i 为中心扩展回文尝试通过比较两侧字符扩展以 i 为中心的回文。只要字符匹配就持续扩展。while (ms[i 1 p[i]] ms[i - 1 - p[i]]) { p[i]; }5、更新最右边界如果以 i 为中心的回文超出了当前右边界 r更新 l 和 r 为新的更长回文的边界。if (i p[i] r) { l i - p[i]; r i p[i]; }6、最终结果转换后字符串中每个索引 i 对应的p[i]存储了以 i 为中心的最大回文半径。四、镜像对称性与三种情况我们解释代码如何处理镜像对称性的三种情况1、情况 1iri 在当前回文内部int mirror l r - i; p[i] min(r - i, p[mirror]);这本质上是通过参考镜像点 j2c−i 来计算 i 处的回文。代码统一处理了情况 1和情况 2情况 1p[mirror] r - i镜像点的回文完全在当前回文内部 → 直接复制完整值。情况 2p[mirror] r - i镜像点的回文超出了边界 r → 只复制到边界 r 为止。p[i] min(r - i, p[mirror]);用一行代码正确处理了以上两种情况。2、情况 3p[mirror] r - i我们仍通过上述min(...)逻辑将p[i]设为r - i但会继续手动扩展while (ms[i 1 p[i]] ms[i - 1 - p[i]]) { p[i]; }这对应情况 3镜像回文恰好触及边界尝试在此基础上继续向外扩展。3、更新区间 [l,r]一旦 i 处的扩展超过了 r立即更新最右侧回文的边界。这保证了 l 和 r 始终是当前已知最长回文的边界为后续迭代的正确镜像计算提供支持。五、马拉车算法的正确性原理要理解为什么马拉车算法能在线性时间内正确计算所有回文子串核心在于对称性以及它如何利用镜像位置避免重复工作。1、回文的对称性回文围绕其中心具有镜像对称性。如果一个回文的中心是center且位置 i 在该回文内部ir那么 i 对应的镜像位置为mirror 2 * center - i2、复用镜像信息如果已知p[mirror] x我们可以直接确定i 周围至少有min(r - i, p[mirror])个字符必然匹配。超出该范围的部分可能匹配也可能不匹配只需尝试扩展即可。这极大节省了时间无需在每个中心从零开始扩展而是从已知长度开始仅在必要时继续向外扩展。3、代码实现① C#include iostream #include vector #include string using namespace std; class Manacher { public: // p[i] 预处理字符串中以 i 为中心的最长回文半径 vectorint p; // 插入 # 分隔符与边界哨兵后的预处理字符串 string ms; // 预处理字符串并执行算法 Manacher(string s) { // 左边界哨兵防止越界 ms ; for (char c : s) { ms # string(1, c); } // 右边界哨兵 ms #$; // 执行马拉车算法 runManacher(); } void runManacher() { int n ms.size(); p.assign(n, 0); int l 0, r 0; // 当前最右回文的左右边界 for (int i 1; i n - 1; i) { // 计算 i 关于中心 (l r)/2 的镜像位置 int mirror l r - i; // 如果 i 在当前回文区间内利用镜像值初始化半径 if (i r) p[i] min(r - i, p[mirror]); // 以 i 为中心向两侧扩展回文 while (ms[i 1 p[i]] ms[i - 1 - p[i]]){ p[i]; } // 如果当前回文超出右边界更新最右回文区间 [l, r] if (i p[i] r) { l i - p[i]; r i p[i]; } } } // 返回原字符串中以 cen 为中心的最长回文长度 // odd 1 → 奇数长度回文odd 0 → 偶数长度回文 int getLongest(int cen, int odd) { // 将原字符串下标映射到预处理字符串下标 int pos 2 * cen 2 !odd; return p[pos]; } // O(1) 判断子串 s[l..r] 是否为回文 bool check(int l, int r) { int len r - l 1; int cen (l r) / 2; return len getLongest(cen, len % 2); } };② Javaclass Manacher { // p[i] radius of longest palindrome centered at i // in transformed string int[] p; // transformed string with # and sentinels String ms; // preprocess the string and run the algorithm Manacher(String s) { // left sentinel ms ; for (char c : s.toCharArray()) { ms # c; } // right sentinel ms #$; // run Manacher’s algorithm runManacher(); } void runManacher() { int n ms.length(); p new int[n]; int l 0, r 0; for (int i 1; i n - 1; i) { // mirror of i around center (l r)/2 int mirror l r - i; // initialize p[i] based on its mirror // if within bounds if (i r) p[i] Math.min(r - i, p[mirror]); // expand palindrome centered at i while (ms.charAt(i 1 p[i]) ms.charAt(i - 1 - p[i])) { p[i]; } // update [l, r] if the palindrome expands // beyond current r if (i p[i] r) { l i - p[i]; r i p[i]; } } } // returns length of longest palindrome centered // at cen in original string // odd 1 → check for odd-length, odd 0 → even-length int getLongest(int cen, int odd) { // map original index to transformed string index int pos 2 * cen 2 (odd 0 ? 1 : 0); return p[pos]; } // checks if s[l..r] is a palindrome in O(1) boolean check(int l, int r) { int len r - l 1; int cen (l r) / 2; return len getLongest(cen, len % 2); } }③ Pythonclass Manacher: # p[i] radius of longest palindrome centered at i # in transformed string def __init__(self, s): # transformed string with # and sentinels self.ms for c in s: self.ms # c self.ms #$ # run Manacher’s algorithm self.p [0] * len(self.ms) self.runManacher() def runManacher(self): n len(self.ms) l r 0 for i in range(1, n - 1): # mirror of i around center (l r)/2 mirror l r - i # initialize p[i] based on its mirror # if within bounds if i r: self.p[i] min(r - i, self.p[mirror]) # expand palindrome centered at i while self.ms[i 1 self.p[i]] \ self.ms[i - 1 - self.p[i]]: self.p[i] 1 # update [l, r] if the palindrome expands # beyond current r if i self.p[i] r: l i - self.p[i] r i self.p[i] # returns length of longest palindrome centered # at cen in original string # odd 1 → check for odd-length, odd 0 → even-length def getLongest(self, cen, odd): # map original index to transformed string index pos 2 * cen 2 (0 if odd else 1) return self.p[pos] # checks if s[l..r] is a palindrome in O(1) def check(self, l, r): length r - l 1 cen (l r) // 2 return length self.getLongest(cen, length % 2)④ C#using System; class Manacher { // p[i] radius of longest palindrome centered at i // in transformed string public int[] p; // transformed string with # and sentinels public string ms; // preprocess the string and run the algorithm public manacher(string s) { ms ; foreach (char c in s) { ms # c; } ms #$; runManacher(); } void runManacher() { int n ms.Length; p new int[n]; int l 0, r 0; for (int i 1; i n - 1; i) { // mirror of i around center (l r)/2 int mirror l r - i; // initialize p[i] based on its mirror // if within bounds if (i r) p[i] Math.Min(r - i, p[mirror]); // expand palindrome centered at i while (ms[i 1 p[i]] ms[i - 1 - p[i]]) { p[i]; } // update [l, r] if the palindrome expands // beyond current r if (i p[i] r) { l i - p[i]; r i p[i]; } } } // returns length of longest palindrome centered // at cen in original string // odd 1 → check for odd-length, odd 0 → even-length public int getLongest(int cen, int odd) { int pos 2 * cen 2 (odd 0 ? 1 : 0); return p[pos]; } // checks if s[l..r] is a palindrome in O(1) public bool check(int l, int r) { int len r - l 1; int cen (l r) / 2; return len getLongest(cen, len % 2); } }⑤ JavaScriptclass Manacher { constructor(s) { // 插入 # 分隔符与边界哨兵后的预处理字符串 this.ms ; for (let c of s) { this.ms # c; } this.ms #$; // p[i] 预处理字符串中以 i 为中心的最长回文半径 this.p Array(this.ms.length).fill(0); // 执行马拉车算法 this.runManacher(); } runManacher() { let n this.ms.length; let l 0, r 0; for (let i 1; i n - 1; i) { // 计算 i 关于中心 (l r)/2 的镜像位置 let mirror l r - i; // 如果 i 在当前回文区间内利用镜像值初始化半径 if (i r) this.p[i] Math.min(r - i, this.p[mirror]); // 以 i 为中心向两侧扩展回文 while (this.ms[i 1 this.p[i]] this.ms[i - 1 - this.p[i]]) { this.p[i]; } // 如果当前回文超出右边界更新最右回文区间 [l, r] if (i this.p[i] r) { l i - this.p[i]; r i this.p[i]; } } } // 返回原字符串中以 cen 为中心的最长回文长度 // odd 1 → 奇数长度回文odd 0 → 偶数长度回文 getLongest(cen, odd) { let pos 2 * cen 2 (odd 0 ? 1 : 0); return this.p[pos]; } // O(1) 判断子串 s[l..r] 是否为回文 check(l, r) { let len r - l 1; let cen Math.floor((l r) / 2); return len this.getLongest(cen, len % 2); } }时间复杂度O(n)马拉车算法能够以线性时间运行原因在于在回文扩展过程中预处理字符串的每个字符最多只会被访问一次同时利用镜像值避免了重复比对与冗余检查。整体算法的操作总量为 O(n)其中 n 为原字符串长度字符串预处理后长度约为 2n3仍属于线性级别。辅助空间复杂度O(n)算法需要额外开辟数组 p[] 存储各位置的回文半径数组长度与预处理字符串成正比约 2n3。同时改造后的预处理字符串也占用 O(n) 空间因此整体额外空间相对于原字符串长度保持线性复杂度。