1. 项目概述为什么我们需要Manacher算法如果你刷过LeetCode或者参加过算法竞赛肯定遇到过“最长回文子串”这道经典题目。最直观的解法是枚举所有可能的子串中心然后向两边扩展时间复杂度是O(n²)。对于较短的字符串这或许可以接受但一旦字符串长度达到10⁵甚至10⁶级别O(n²)的算法就会立刻超时。这时Manacher算法就登场了——它能在O(n)的线性时间内找出一个字符串中所有可能的回文子串信息。我第一次接触Manacher是在准备一场关键的算法面试时当时觉得这个算法名字听起来很“唬人”原理似乎也很绕。但真正理解并亲手用C实现一遍后才发现它的设计极其精妙核心思想是利用了回文串的对称性来避免重复计算。这篇文章我就从一个C开发者的实战角度带你彻底吃透Manacher算法从暴力解法到算法优化再到手把手实现最后分析时间空间复杂度。无论你是为了面试刷题还是为了提升算法内功这篇近万字的详解都能让你一次搞懂。2. 核心思路拆解从暴力到智慧的跨越2.1 问题定义与暴力解法首先明确我们要解决的问题给定一个长度为n的字符串s找出其所有回文子串或者至少找出最长的回文子串。一个字符串是回文串意味着它正着读和反着读是一样的比如 “aba”, “abba”。最朴素的暴力解法有两种枚举所有子串双重循环枚举所有起始位置i和结束位置j判断s[i…j]是否是回文。判断回文需要O(j-i1)时间总复杂度高达O(n³)。中心扩展法这是更常见的优化。遍历每个可能的“中心点”共有n个奇数长度中心n-1个偶数长度中心从中心向两边扩展直到字符不匹配。这种方法的时间复杂度是O(n²)。中心扩展法的C代码大概长这样int expandAroundCenter(const string s, int left, int right) { while (left 0 right s.size() s[left] s[right]) { left--; right; } return right - left - 1; // 返回回文串长度 } // 主函数中需要分别处理奇偶中心这个算法在面试中常作为热身题但它O(n²)的复杂度在面对大数据时依然不够看。我们需要思考在中心扩展的过程中是否存在大量重复计算2.2 Manacher算法的核心洞察对称性与状态复用Manacher算法的天才之处在于它发现并利用了回文串的一个关键性质对称性。假设我们已知一个以位置center为中心、右边界为right的很长的回文串。现在我们要计算位置ii在center右侧且在right左侧的回文半径。由于回文串的对称性i关于center的对称点是j 2 * center - i。关键推理如果以j为中心的回文串完全被包含在以center为中心的大回文串内部即j的回文左边界没有超过大回文串的左边界那么根据对称性i的回文半径至少等于j的回文半径。因为大回文串内部的镜像区域是完全相同的。这个“至少”非常重要它让我们能直接获得一个安全的起始扩展半径而不是每次都从1开始扩展。如果j的回文左边界超出了大回文串的范围那么i的回文半径最多只能扩展到right - i的位置因为超出部分无法利用对称性保证。这就是Manacher算法的核心维护一个当前已知的、右边界最靠右的回文串利用它的对称性来加速后续中心点的计算。2.3 奇偶统一处理插入分隔符的技巧中心扩展法需要分别处理奇偶长度回文串这增加了代码复杂度。Manacher采用了一个非常巧妙的预处理技巧在原始字符串的每个字符之间以及首尾插入一个相同的、不会在原串中出现的分隔符常用#。例如原始字符串s “abba”预处理后变成t “#a#b#b#a#”。这样做有两个巨大好处统一奇偶性新字符串t的长度总是奇数2*n 1。这样无论是原始字符串中的奇数长度回文如”aba”还是偶数长度回文如”abba”在t中都对应一个奇数长度的回文串分别对应”#a#b#a#”和”#a#b#b#a#”。我们只需要处理奇数长度回文这一种情况。简化边界判断由于我们在首尾也插入了分隔符在扩展时无需特殊处理边界因为边界字符一定是#不可能匹配循环会自动终止。预处理后算法的目标就变成了对于新字符串t计算一个数组p其中p[i]表示以t[i]为中心的最长回文子串的半径长度包含中心点。例如对于”#a#b#a#”中心b处的p值为4回文串是”#a#b#a#”半径是4。3. 算法流程与C实现详解理解了核心思想我们来看具体的算法步骤和C实现。我会逐行解释并附上完整的、可运行的代码。3.1 算法步骤分解假设我们已经得到了预处理后的字符串t长度为mm 2*n 1。我们需要计算数组p[0…m-1]。我们维护两个关键变量center: 当前已知的、右边界最靠右的回文串的中心位置。right: 该回文串的右边界索引开区间即实际右边界是right-1。算法从i0遍历到im-1初始化p[i]如果i right说明当前位置i不在任何已知回文串的“保护”范围内我们没有任何先验信息只能从1开始朴素扩展。所以设p[i] 1。如果i right说明i在某个已知回文串内部。找到i关于center的对称点j 2*center - i。那么p[i]至少可以取min(p[j], right - i)。这是因为p[j]是以j为中心的回文半径。如果以j为中心的回文串完全包含在大回文串内那么p[i]可以直接等于p[j]。right - i是i到大回文串右边界的距离。即使j的回文串超出了大回文串左边界i的回文串也不可能超过right因为超出部分无法保证对称性。 取两者最小值是安全的起始半径。中心扩展在确定了p[i]的初始值后我们尝试向两边扩展。只要满足i - p[i] 0 i p[i] m t[i - p[i]] t[i p[i]]就说明可以继续扩展p[i]。更新维护的回文串扩展完成后如果以i为中心的回文串的右边界i p[i]超过了当前的right说明我们找到了一个更靠右的回文串。更新center i和right i p[i]。3.2 完整C代码实现下面是我在项目中常用的、经过优化的C实现。代码包含了预处理、核心算法以及后处理获取原始字符串最长回文子串的功能。#include iostream #include string #include vector #include algorithm using namespace std; class Manacher { public: // 预处理将原字符串s转换为添加分隔符的新字符串t // 例如 abba - ^#a#b#b#a#$ // 这里在首尾添加了^和$作为哨兵可以避免边界检查 string preProcess(const string s) { int n s.length(); if (n 0) return ^$; string t ^; for (int i 0; i n; i) { t #; t s[i]; } t #$; return t; } // 核心Manacher算法返回预处理字符串t的半径数组p vectorint manacher(const string t) { int m t.length(); vectorint p(m, 0); int center 0, right 0; for (int i 1; i m - 1; i) { // 跳过首尾哨兵 int i_mirror 2 * center - i; // i关于center的对称点 // 关键步骤利用对称性确定p[i]的初始值 if (right i) { p[i] min(right - i, p[i_mirror]); } else { p[i] 0; // 不在已知回文串保护范围内从0开始 } // 尝试中心扩展 while (t[i p[i] 1] t[i - p[i] - 1]) { p[i]; } // 如果扩展后的右边界超过了当前right更新center和right if (i p[i] right) { center i; right i p[i]; } } return p; } // 获取原始字符串的最长回文子串 string longestPalindrome(const string s) { if (s.empty()) return ; string t preProcess(s); vectorint p manacher(t); // 找到半径最大的中心点 int maxLen 0; int centerIndex 0; for (int i 1; i t.length() - 1; i) { if (p[i] maxLen) { maxLen p[i]; centerIndex i; } } // 将预处理字符串中的中心位置映射回原始字符串 // 在t中原始字符出现在奇数索引位置1, 3, 5, ... // 半径maxLen对应原始字符串的长度就是maxLen int start (centerIndex - maxLen) / 2; return s.substr(start, maxLen); } // 获取所有回文子串的数量可选功能 int countPalindromes(const string s) { if (s.empty()) return 0; string t preProcess(s); vectorint p manacher(t); int total 0; // 对于预处理字符串t中的每个位置i跳过哨兵 // p[i]表示以t[i]为中心的最长回文半径包含中心 // 那么以t[i]为中心的回文子串数量就是p[i]半径是多少就有多少个不同半径的回文串 for (int i 1; i t.length() - 1; i) { total p[i]; } // 注意这里计算的是预处理字符串中的回文子串数量 // 如果需要原始字符串中的数量需要根据奇偶性调整 return total; } }; // 测试函数 int main() { Manacher solver; // 测试用例1普通情况 string s1 babad; cout 原始字符串: s1 endl; cout 最长回文子串: solver.longestPalindrome(s1) endl; cout 回文子串总数: solver.countPalindromes(s1) endl; cout endl; // 测试用例2偶数长度回文 string s2 cbbd; cout 原始字符串: s2 endl; cout 最长回文子串: solver.longestPalindrome(s2) endl; cout endl; // 测试用例3全相同字符 string s3 aaaa; cout 原始字符串: s3 endl; cout 最长回文子串: solver.longestPalindrome(s3) endl; cout 回文子串总数: solver.countPalindromes(s3) endl; return 0; }3.3 代码逐行解析与关键点预处理函数preProcess我选择了^和$作为首尾哨兵。这比单纯用#更好因为^和$通常不会出现在输入字符串中而且它们明确标记了字符串的边界在扩展时while循环遇到它们会自动停止无需额外的索引检查。预处理后的字符串格式为^#a#b#b#a#$。注意原始字符a出现在索引1, 3, 5…的位置奇数索引而#出现在偶数索引除了首尾的^和$。核心算法函数manachervectorint p(m, 0)p[i]表示以t[i]为中心的最长回文子串的半径从中心到一边的字符数包含中心自身。例如对于回文串”#a#b#a#”中心b的p值为3半径包含b、左边的#a和右边的#a但注意我们计算的是半径长度不是直径。int i_mirror 2 * center - i计算对称点。这是利用中点公式center (i i_mirror) / 2。if (right i)判断i是否在[center - radius, center radius]这个当前最右回文串的范围内。注意right是开区间所以是而不是。p[i] min(right - i, p[i_mirror])这是算法的精髓。right - i是i到右边界的距离p[i_mirror]是对称点的半径。取最小值确保了我们的初始扩展不会超出已知的“安全区域”。while循环进行中心扩展。注意我写的是t[i p[i] 1] t[i - p[i] - 1]这是因为p[i]初始值可能为0我们从中心向左右各扩展一位开始比较。这种写法比先赋值再while循环内p[i]更清晰。更新center和right只有当i p[i] right时才更新保证了right是单调不减的这是算法O(n)复杂度的关键。后处理与映射在longestPalindrome函数中我们找到p数组中的最大值maxLen及其索引centerIndex。关键映射公式原始字符串中的起始位置start (centerIndex - maxLen) / 2。为什么因为在预处理字符串t中原始字符的索引都是奇数。假设t中回文中心在索引i半径为maxLen那么这个回文串在t中的范围是[i-maxLen, imaxLen]。这个范围内的奇数索引对应原始字符串的字符。第一个奇数索引是i-maxLen1如果i-maxLen是偶数或i-maxLen如果i-maxLen是奇数。通过观察和推导可以证明(i - maxLen) / 2就是原始字符串中的起始位置。回文串在原始字符串中的长度就是maxLen。因为预处理字符串中每个原始字符前后都有一个#所以半径maxLen对应的原始字符串长度就是maxLen你可以用几个例子验证一下。4. 时间复杂度与空间复杂度分析4.1 为什么是O(n)这是Manacher算法最令人惊叹的地方。表面上看我们有一个外层循环遍历n个位置内层还有一个while循环进行扩展似乎是O(n²)。但关键在于right这个变量是单调不减的且每次while循环成功扩展都会使right增加。我们可以这样思考算法中的字符比较只发生在while循环的t[i p[i] 1] t[i - p[i] - 1]这一行。每次比较成功p[i]增加1同时right即i p[i]也至少增加1。而right最多从0增长到m预处理字符串长度。因此整个算法过程中字符比较的总次数是O(m)的也就是O(n)。更形式化的证明可以采用摊还分析每个字符最多被成功比较一次扩展right也可能在p[i]被赋初值时“跳过”而未被比较。所以总操作次数是线性的。4.2 空间复杂度我们需要一个长度为mm 2n 3的数组p来存储半径信息所以空间复杂度是O(n)。预处理字符串t也需要O(n)空间。总体是O(n)。5. 边界情况与注意事项在实际编码和调试中我踩过不少坑这里总结几个关键点5.1 预处理字符串的哨兵选择我选择^和$作为首尾哨兵而不是像很多教程那样只用#。这样做有两个好处避免边界检查在while循环中当i p[i] 1或i - p[i] - 1超出字符串范围时访问t的哨兵字符^或$它们不可能相等循环自然终止。否则你需要写i p[i] 1 m i - p[i] - 1 0这样的条件代码更冗长。统一索引计算p数组的长度是m我们遍历从1到m-2避开了哨兵。这样p[i]的值就是准确的半径不需要在映射时做±1的调整。5.2 奇偶回文的统一处理验证为了确保你真正理解了预处理的作用可以手动验证几个例子奇数回文”aba”-”^#a#b#a#$”。在t中以b索引4为中心p[4]4对应原始字符串中长度为3的回文”aba”。偶数回文”abba”-”^#a#b#b#a#$”。在t中两个b之间的#索引5是中心p[5]4对应原始字符串中长度为4的回文”abba”。你会发现无论原始回文是奇是偶在t中都对应一个奇数长度的回文且p[i]的值正好是原始回文串的长度。5.3 数组下标与半径的定义这里最容易混淆。在我的实现中p[i]半径表示从中心t[i]向一侧扩展的字符数包含中心自身。所以回文串的总长度是2 * p[i] - 1在预处理字符串中。为什么while循环中是t[i p[i] 1] t[i - p[i] - 1]因为当前已经确认了半径为p[i]的回文我们要检查的是半径再扩展1是否还满足回文条件。所以比较的是中心向外第p[i]1个字符。如果你看到其他实现中p[i]定义不同比如表示直径或半长那么循环条件和映射公式都会不同。关键是要自洽理解并坚持一种定义方式。5.4 性能优化小技巧避免字符串拼接在preProcess中我使用了来构建新字符串。对于超长字符串可以预分配空间string t; t.reserve(2 * n 3);然后使用t.push_back()效率更高。减少除法运算在映射回原始字符串时(centerIndex - maxLen) / 2涉及除法。如果性能极其敏感可以确保centerIndex和maxLen都是整数且注意整数除法的特性。并行计算考虑Manacher算法本质是顺序的因为i依赖之前计算的center和right。所以不适合并行化。如果要在多核环境下处理超长字符串可能需要考虑其他思路或算法变种。6. 常见问题与调试技巧6.1 为什么我的程序输出不对首先检查预处理字符串是否正确。打印出t看看是不是你期望的格式。例如对于输入”a”t应该是”^#a#$”。其次在核心算法中最可能出错的是while循环的条件和p[i]的更新。确保初始赋值p[i]时当i right取min(right - i, p[i_mirror])。while循环比较的是t[i p[i] 1]和t[i - p[i] - 1]注意是1和-1不是p[i]。更新right时是i p[i]不是i p[i] - 1。6.2 如何处理空字符串或单字符字符串我的实现在preProcess中已经处理了空字符串情况返回”^$”。对于单字符字符串算法也能正确工作。但要注意在longestPalindrome中如果输入为空我直接返回空字符串避免后续访问越界。6.3 如何获取所有回文子串而不仅仅是最长的p数组包含了所有信息。对于预处理字符串t中的每个位置i中心以它为中心的回文子串有p[i]个半径从1到p[i]。但注意这些回文子串在t中要映射回原始字符串需要根据中心位置是原始字符还是#来区分奇偶。一个更直接的方法是在得到p数组后遍历原始字符串的每个可能中心包括字符位置和字符之间的位置根据p值计算出对应的回文串在原串中的起始和结束位置。具体来说对于奇数中心对应原始字符位置i在t中的索引是2*i2考虑我们的预处理方式^#a#b#$第一个字符a在t的索引2。那么半径r p[2*i2]对应原始字符串中从i - r/2到i r/2的回文串。对于偶数中心对应字符间位置计算类似但索引不同。6.4 内存使用能更优吗理论上我们不需要同时存储整个p数组。因为算法只依赖p[i_mirror]而i_mirror总是小于i当i在right左侧时。但为了代码清晰和后续查询比如找所有回文通常还是保留整个数组。如果只找最长回文可以只记录最大值及其索引不存整个p数组。7. 算法变体与应用场景7.1 查找所有回文子串数量如我之前代码所示countPalindromes函数可以统计预处理字符串中所有回文子串数量每个中心i贡献p[i]个。但要注意这统计的是t中的回文包括那些中心是#的。如果只想统计原始字符串中的回文数量需要过滤掉那些完全由#组成的回文实际上就是偶数长度回文被重复计算的部分。更准确的计算公式是原始字符串中回文子串总数 Σ(ceil(p[i]/2))其中i遍历t中所有原始字符对应的位置。7.2 判断任意子串是否为回文如果我们预处理了整个字符串并得到了p数组就可以在O(1)时间内回答任意查询[l, r]是否是回文。方法是将原始区间[l, r]映射到预处理字符串中的中心c和半径len然后检查p[c]是否足够大。具体来说对于奇数长度查询l和r同奇偶中心c l r在原始索引下然后检查p[c] (r-l)/2 1。对于偶数长度查询需要小心处理因为中心在两个字符之间。7.3 在流数据中的应用经典Manacher需要整个字符串已知。如果数据是流式的例如从网络逐段接收需要支持在字符串末尾添加字符并动态维护回文信息这就是“在线Manacher”问题。这通常需要结合后缀自动机或其他数据结构复杂度会更高。7.4 与其他算法的对比动态规划用dp[i][j]表示s[i…j]是否是回文时间复杂度O(n²)空间复杂度O(n²)可优化到O(n)。比中心扩展法更差通常不用于此问题。后缀数组/后缀自动机可以解决但过于复杂O(n log n)或O(n)但常数大。哈希二分通过字符串哈希可以在O(1)时间内比较子串是否相等对每个中心二分搜索最大半径总复杂度O(n log n)。比Manacher慢但实现简单。在实际面试或竞赛中Manacher通常是首选因为它既高效又相对容易实现一旦理解。8. 实战练习与测试用例光说不练假把式。这里提供一些测试用例你可以用它们验证你的实现void testManacher() { Manacher solver; struct TestCase { string input; string expected; int expectedCount; // 回文子串总数预处理字符串中 }; vectorTestCase tests { {, }, // 空字符串 {a, a}, // 单字符 {aa, aa}, // 全相同偶数长度 {ab, a}, // 无回文取第一个字符或b也可 {aba, aba}, // 标准奇数回文 {abba, abba}, // 标准偶数回文 {babad, bab}, // 注意aba也是最长但算法返回找到的第一个 {cbbd, bb}, // 最长回文是bb {abcde, a}, // 无回文单字符 {aaaa, aaaa}, // 全相同多个最长回文 {racecar, racecar}, // 经典回文 {abacdfgdcaba, aba}, // 注意不是整个串回文 }; for (const auto test : tests) { string result solver.longestPalindrome(test.input); if (result ! test.expected) { cout 测试失败: 输入\ test.input \, 期望\ test.expected \, 实际\ result \ endl; } else { cout 测试通过: 输入\ test.input \, 结果\ result \ endl; } } }运行这些测试确保你的实现在各种边界情况下都能正确工作。特别是空字符串、单字符、全相同字符这些边缘情况往往是面试官考察的重点。9. 从理论到实践我踩过的那些坑最后分享一些我在实际使用Manacher算法时积累的经验索引从0开始还是1开始这可能是最让人头疼的。我强烈建议在纸上画图用一个小例子比如”aba”手动模拟算法过程标出每个索引和p值。一旦你理清了索引关系代码就清晰了。我的经验是坚持使用0-based索引但在预处理时添加明确的哨兵这样逻辑最清晰。while循环的越界检查如果你不用哨兵那么while循环必须检查索引是否越界while (i - p[i] 0 i p[i] n s[i-p[i]] s[ip[i]])。注意这里是i ± p[i]不是i ± p[i] ± 1取决于你的p[i]定义。用哨兵可以简化这个条件。更新right的时机一定要在扩展完成后再更新right。有些初学者会在while循环内更新这是错误的因为p[i]在循环中可能增加多次。对称点的计算i_mirror 2 * center - i这个公式要记牢。当center和i都是整数时i_mirror可能是小数吗不会因为i和center的奇偶性相同都在预处理字符串的奇数索引或偶数索引上所以i_mirror也是整数。性能测试对于长度10⁶的随机字符串我的C实现在现代CPU上能在几十毫秒内完成。如果发现性能不符合预期检查是否有不必要的字符串拷贝比如传值而不是传引用或者是否在循环中调用了length()这样的函数应该事先存到变量中。Manacher算法是一个典型的“想通了就很简单想不通就一头雾水”的算法。我第一次学习时花了整整一个下午才完全理解。但一旦掌握它就成为你解决回文问题的利器。在面试中如果你能清晰地解释Manacher的原理并写出正确代码绝对是一个大大的加分项。