1. 项目概述从“暴力”到“优雅”的字符串匹配进化之路如果你刷过一些算法题尤其是在处理字符串相关的问题时一定对“超时”这两个字深恶痛绝。一个看似简单的模式匹配用最直观的双重循环去写在小数据量下跑得飞快一旦数据规模上去立刻给你一个无情的“TLE”Time Limit Exceeded。我刚开始接触算法时就无数次栽在这个坑里。后来才知道字符串匹配这片江湖早已不是“暴力匹配”一家独大的天下了。三位“高手”——KMP、扩展KMP和Manacher各自掌握着独门绝技能让你在面对诸如“寻找子串”、“最长回文子串”这类问题时从“苦苦挣扎”变得“游刃有余”。“kuangbin带你飞”这个专题计划在算法竞赛圈子里可以说是无人不知。它就像一份精心编排的武功秘籍把各个算法知识点分门别类带着学习者一路打怪升级。专题十六聚焦的正是字符串处理中这三个核心且经典的算法。KMP解决的是高效的单模式串匹配问题它教会我们如何利用已经匹配的信息避免主串指针的回退实现线性的时间复杂度。扩展KMP则可以看作是KMP思想的延伸它不仅能解决匹配问题还能一次性求出主串所有后缀与模式串的最长公共前缀在处理某些复杂问题时非常有用。而Manacher算法则是专门为“寻找最长回文子串”这个问题而生的“神器”它用巧妙的中心扩展和对称性将这个问题的时间复杂度也降到了线性。掌握这三个算法绝不仅仅是为了通过几道算法题。它们背后蕴含的“利用已有信息避免重复计算”的思想是优化算法、提升程序效率的核心思维。无论是文本编辑器的查找功能、生物信息学的基因序列比对还是网络协议中的数据包解析都能看到这些算法思想的影子。接下来我就结合自己刷题和教学的经验把这三种算法的核心原理、实现细节以及那些容易踩的坑掰开揉碎了讲给你听。2. 核心算法原理深度拆解理解“为什么”比记住“怎么做”更重要很多人在学习这些算法时容易陷入一个误区死记硬背模板代码。结果就是题目稍微一变或者需要自己推导关键数组时就束手无策了。我们必须从原理层面理解它们明白每一个步骤背后的意图才能做到举一反三。2.1 KMP算法失配时模式串该滑多远KMP算法的核心在于一个叫做next数组有些资料称为prefix table或部分匹配表的东西。它解决了暴力匹配中最大的浪费当主串S[i]和模式串P[j]失配时暴力匹配会将i回溯j归零重新开始。而KMP算法发现i完全不需要回溯只需要将j移动到某个位置next[j]即可。next数组的定义对于模式串Pnext[j]的值是P[0...j-1]这个子串中最长的、相等的前缀和后缀的长度。前缀指除了最后一个字符以外字符串的全部头部组合。后缀指除了第一个字符以外字符串的全部尾部组合。举个例子模式串P “ababc”当j4(指向字符‘c’)我们看P[0...3]即“abab”。它的前缀有“a”,“ab”,“aba”。它的后缀有“b”,“ab”,“bab”。共同的前缀和后缀是“ab”长度为2。所以next[4] 2。这个值的意义是什么它意味着在位置j失配时P[0...next[j]-1]这段前缀已经和主串中对应位置的字符匹配成功了。所以我们可以直接把模式串的j指针移动到next[j]让这段已经匹配好的前缀对齐主串然后从P[next[j]]开始继续比较。主串的指针i完全不动。计算next数组的过程本身就是一个“模式串自我匹配”的过程是理解KMP的关键。我们可以用两个指针i和j其中i指向当前待计算next值的位置后缀的末尾j指向前缀的末尾同时也是next值。初始化next[0] -1(或0取决于实现习惯-1的写法更通用)i 0, j -1。如果j -1或P[i] P[j]则next[i] j。这表示匹配成功最长公共前后缀长度增加。如果P[i] ! P[j]则令j next[j]。这一步是精髓它利用已经计算好的next值进行回溯寻找更短的、可能匹配的前缀。注意next数组的计算是KMP中最容易出错的部分。一定要理解j next[j]这个操作它和主匹配过程中的操作是完全同构的都是在失配时利用已知信息跳转。2.2 扩展KMP算法一次性看清所有后缀的“亲戚关系”扩展KMPZ-algorithm要解决的问题略有不同给定一个字符串S求出S的每一个后缀与S本身的最长公共前缀LCP长度这个长度数组通常记为Z[i]。其中Z[0]通常定义为0或n长度。这个算法同样是线性时间复杂度其核心思想是维护一个“匹配箱”或称“Z-box”[L, R]这个区间代表了当前已知的、与前缀匹配的最右端的一个子串。L和R记录了这个匹配子串的左右边界。对于当前位置i如果i R说明当前位置在已知匹配箱之外我们只能用最朴素的暴力方法逐个字符比较计算Z[i]然后更新L和R。如果i R说明i在已知匹配箱内。那么S[i...R]这段是S[0...R-L]的复制。我们可以利用已经计算好的Z[i-L]来快速推断Z[i]的初始值。但要注意一个边界推断出的长度不能超过R-i1超过的部分仍需暴力检查。扩展KMP可以用来高效解决很多问题比如寻找字符串的所有匹配位置通过计算模式串P‘#’主串S的Z数组、寻找字符串的最小周期等。它提供了一种全局的“自我相似性”视图。2.3 Manacher算法巧用对称一击即中的回文判官寻找一个字符串中的最长回文子串最直观的方法是枚举所有中心点向两边扩展中心扩展法。但这样时间复杂度是O(n²)。Manacher算法的妙处在于它通过插入分隔符如‘#’将奇偶长度的回文统一为奇数长度处理并利用回文串的对称性避免了大量重复的扩展计算。算法的核心是维护一个回文半径数组p[i]以及当前能延伸到最右端的回文中心C和其右边界R。p[i]表示以i为中心处理后的新串T中的最长回文半径包含中心点。C和R表示当前所有回文子串中右边界最靠右的那个回文子串的中心和右边界。关键推导当我们要计算p[i]时如果i R无法利用对称性只能从1开始中心扩展。如果i R那么i关于中心C的对称点是j 2*C - i。我们可以利用p[j]来快速获得p[i]的一个下限。如果p[j]对应的回文串左边界在C的回文串左边界之内即j - p[j] 1 2*C - R那么根据对称性p[i]至少等于p[j]。如果p[j]对应的回文串左边界超出了C的回文串左边界那么p[i]至少等于R - i 1。综合起来p[i]的初始值就是min(p[j], R - i 1)。在得到初始半径后再尝试向两边扩展并更新C和R。这个算法的精妙之处在于大部分情况下步骤2直接给出了p[i]的最终值无需扩展。只有当下限值刚好触达边界R时才需要继续扩展探索。这保证了算法是线性的。3. 算法实现与代码细节从理论到落地的关键一步理解了原理我们来看看如何用代码实现。这里我以C为例因为这是算法竞赛中最常用的语言但逻辑是通用的。3.1 KMP算法的标准实现与next数组优化首先实现计算next数组的函数。这里采用next[0] -1的版本它在编码时逻辑更清晰。// 计算模式串p的next数组 void getNext(const string p, vectorint next) { int n p.size(); next.resize(n); next[0] -1; int i 0, j -1; while (i n - 1) { // 注意循环条件计算到next[n-1]即可 if (j -1 || p[i] p[j]) { i; j; // 标准next数组 next[i] j; // 优化版next数组有时称为nextval // if (p[i] ! p[j]) next[i] j; // else next[i] next[j]; } else { j next[j]; } } }实操心得while (i n - 1)这个条件需要特别注意。因为我们在循环体内是先i; j;再赋值所以i最大会被增加到n-1恰好计算出next[n-1]。如果写成i n则会越界。接下来是KMP匹配的主函数// KMP匹配返回所有匹配起始位置 vectorint kmpSearch(const string s, const string p) { vectorint next; getNext(p, next); vectorint res; int i 0, j 0; // i主串指针j模式串指针 int n s.size(), m p.size(); while (i n) { if (j -1 || s[i] p[j]) { i; j; } else { j next[j]; } if (j m) { // 完全匹配 res.push_back(i - j); // 记录匹配起始位置 j next[j]; // 继续寻找下一个匹配注意这里jmnext[m]需要预先计算或理解为0 } } return res; }关于next数组的优化标准next数组在某些情况下仍有小优化空间。例如模式串“aaaaab”在j4字符‘a’失配时next[4]3跳转后还是‘a’必然继续失配会连续跳转多次。优化版常叫nextval在计算next[i]时如果发现p[i] p[j]则直接让next[i] next[j]一步跳转到最终可能匹配的位置。这在模式串字符重复度高时能提升常数时间性能。3.2 扩展KMPZ算法的实现模板扩展KMP的实现需要仔细处理边界特别是“匹配箱”的维护。// 计算字符串s的Z数组 vectorint getZArray(const string s) { int n s.size(); vectorint z(n, 0); int l 0, r 0; // [l, r]是最右匹配箱 for (int i 1; i n; i) { if (i r) { // i在匹配箱内可以利用对称性 z[i] min(z[i - l], r - i 1); } // 暴力扩展注意边界 while (i z[i] n s[z[i]] s[i z[i]]) { z[i]; } // 更新最右匹配箱 if (i z[i] - 1 r) { l i; r i z[i] - 1; } } // 通常z[0]定义为0或n这里我们按算法逻辑保持0有时题目要求设为n // z[0] n; // 根据需求决定 return z; }一个经典应用寻找文本T中所有模式串P的出现位置。我们可以构造新字符串S P ‘#’ T然后计算S的Z数组。对于T部分即i m的位置其中m是P的长度如果Z[i] m那么就找到了一个匹配起始位置是i - m - 1。3.3 Manacher算法的实现与回文复原Manacher的实现需要先对原字符串进行预处理插入分隔符。// 预处理将原字符串s转换为包含分隔符的新字符串t string preProcess(const string s) { int n s.size(); if (n 0) return ^$; // 边界处理 string t ^; for (int i 0; i n; i) { t #; t s[i]; } t #$; return t; } // Manacher算法主体返回最长回文子串的长度 int manacher(const string s) { string t preProcess(s); int len t.size(); vectorint p(len, 0); int C 0, R 0; // 中心与右边界 int maxLen 0; // 记录最长半径 for (int i 1; i len - 1; i) { // 跳过首尾的‘^’和‘$’ int i_mirror 2 * C - i; // 计算i关于C的对称点 // 利用对称性初始化p[i] if (R i) { p[i] min(R - i, p[i_mirror]); } else { p[i] 0; } // 中心扩展 while (t[i 1 p[i]] t[i - 1 - p[i]]) { p[i]; } // 更新最右回文串中心C和边界R if (i p[i] R) { C i; R i p[i]; } // 更新最大回文半径 maxLen max(maxLen, p[i]); } // 在原串s中最长回文子串的长度等于maxLen return maxLen; }如果需要输出最长回文子串本身可以在更新maxLen时记录中心点centerIndex i。算法结束后根据centerIndex和maxLen可以反向映射回原字符串s截取出子串。映射关系是原串中的中心位置为(centerIndex - maxLen - 1) / 2长度为maxLen。4. 典型应用场景与题目实战解析懂了原理和代码我们得知道它们能用来干什么。下面结合LeetCode和ACM的经典题目看看如何运用这三个算法。4.1 KMP的实战不仅仅是匹配题目1实现 strStr() (LeetCode 28)这是KMP最直接的应用。直接套用上面的kmpSearch函数找到第一个匹配位置返回即可。这道题是检验KMP实现正确性的试金石。题目2重复的子字符串 (LeetCode 459)判断一个字符串是否可以由它的一个子串重复多次构成。一个巧妙的解法利用了KMP的next数组。假设字符串s长度为n计算其next数组。如果next[n] 0且n % (n - next[n]) 0那么字符串就是由长度为n - next[n]的子串重复构成的。原理n - next[n]就是最小重复单元的长度。如果整个字符串能被这个长度整除说明它是重复的。题目3最短回文串 (LeetCode 214)给定一个字符串s你可以在它的前面添加字符使其成为回文串。找到最短的回文串。一个高效解法是构造字符串t s ‘#’ reverse(s)然后计算t的KMP next数组。next[t.length()]的值就是s的前缀中与s的后缀匹配的最长长度。那么我们需要补充的字符就是s中剩余部分的反转。4.2 扩展KMP的实战全局视角下的匹配题目查找字符串中所有出现位置如前所述构造P#T求Z数组是比KMP更直观的解法。KMP需要两个阶段求next和匹配而Z算法一步到位得到所有信息。题目字符串的周期对于一个字符串s如果存在一个字符串t使得s是t重复多次的前缀那么t就是s的一个周期。利用Z数组我们可以轻松找到所有可能的周期长度。对于长度len如果len能整除n且Z[len] n - len那么len就是一个周期长度。这比用KMP的next数组判断更直观。4.3 Manacher的实战回文问题的“终结者”题目1最长回文子串 (LeetCode 5)这是Manacher算法的招牌题目。直接用上面的模板在更新maxLen时记录下中心点centerIndex最后根据映射关系从原字符串中提取子串即可。时间复杂度O(n)远优于中心扩展法的O(n²)。题目2回文子串的个数 (LeetCode 647)计算一个字符串中有多少个回文子串。用Manacher算法求出每个位置i的回文半径p[i]后对于处理后的字符串T以T[i]为中心的回文串数量在原串中就是(p[i] 1) / 2。解释在T中回文半径p[i]包含了分隔符‘#’。以i为中心长度为1, 3, 5, ..., p[i]的回文串都是有效的对应原串中长度为0, 1, 2, ...的回文串。但我们需要的是原串中的回文串且原串中回文串中心可能在字符上也可能在字符间对应T中的字符位和‘#’位。一个简单的结论是将T中每个中心点求得的p[i]相加后除以2就是原串中所有回文子串的个数。更稳妥的做法是遍历p数组对每个p[i]累加p[i] / 2如果T[i]是‘#’对应原串偶数长度回文或(p[i] 1) / 2如果T[i]是字符对应原串奇数长度回文。题目3分割回文串 II (LeetCode 132)给定一个字符串s将s分割成一些子串使每个子串都是回文串。返回符合要求的最少分割次数。这是一个动态规划问题。我们可以先用Manacher算法或者普通的中心扩展法预处理出一个二维布尔数组isPal[i][j]表示s[i...j]是否是回文串。然后进行DPdp[i]表示s[0...i]的最小分割次数。状态转移方程为如果s[0...i]整体是回文dp[i]0否则dp[i] min(dp[j] 1)其中j i且s[j1...i]是回文。预处理回文信息时Manacher算法能提供O(n²)的预处理信息通过每个中心扩展但更常见的做法是用中心扩展法O(n²)预处理因为DP本身也是O(n²)。Manacher在这里的优势是常数更小。5. 常见“坑点”与调试技巧实录即使理解了算法实现时也难免出错。下面是我和学生们常遇到的一些问题。5.1 KMP算法常见问题问题1next数组计算死循环或越界。原因循环条件或指针更新顺序错误。特别是在j next[j]这一步如果next[j]计算错误比如为负或等于自身可能导致无限循环。排查用一个小例子如“abab”手动模拟打印出每一步的i, j, next[i]值。确保在p[i]p[j]时是先i, j再赋值next[i]j。问题2匹配时漏掉重叠的匹配。原因找到一个完全匹配j m后j的回退位置不对。如果直接j0会漏掉像主串“aaaaa”中找模式串“aa”这种重叠匹配。解决找到匹配后执行j next[j]。这就要求我们的next数组长度至少为m1即需要计算出next[m]的值。在getNext函数中循环条件应为i m或i m但最后额外处理一次确保next[m]被正确计算。问题3优化版nextval数组理解错误。现象使用了优化版nextval后匹配结果反而错了。分析优化版是在计算next数组的过程中进行的优化而不是先算出标准next再转换。代码中的注释部分展示了两种写法。务必理解优化逻辑是如果p[i] p[j]那么next[i]应该直接等于next[j]因为即使跳转到j由于字符相同依然会失配不如一步到位。5.2 扩展KMP算法常见问题问题1Z数组计算错误特别是边界r的更新。关键点z[i] min(z[i - l], r - i 1);这一行是核心。i-l是对称点z[i-l]是对称点的已知匹配长度。但这个长度不能超过当前匹配箱的右边界r否则超出的部分我们尚未验证所以要用min。调试在循环内打印i, l, r, z[i]的值对照一个简单字符串如“aabcaabx”的Z数组正确值一步步检查。问题2处理“P#T”结构时索引映射混乱。技巧明确新字符串S的长度是m 1 n。S[0...m-1]是PS[m]是分隔符‘#’S[m1...mn]是T。计算Z数组后对于i在[m1, mn]区间如果Z[i] m则T中的匹配起始位置是(i - (m1)) - m不对应该是i - (m1)是T中对应字符的索引但匹配是从这个索引往前推m个字符吗仔细想当Z[i] m时意味着从S[i]开始的m个字符和S[0...m-1]即P匹配。S[i]对应T中的位置是i - (m1)。所以匹配在T中的起始位置就是i - (m1)。不需要再减m因为Z[i]表示的是从i开始匹配的长度。5.3 Manacher算法常见问题问题1预处理字符串后回文半径到原字符串的映射搞错。牢记公式设原串s预处理后串tt中下标为i的字符非‘#’对应原串下标为(i-1)/2。最长回文子串在原串中的中心位置为(centerIndex - 1 - maxLen) / 2我们来推导在t中回文串实际覆盖的字符范围是[centerIndex - maxLen, centerIndex maxLen]。这个范围内的‘#’和字符交替。原串中的回文串起始位置对应t中第一个非‘#’字符的位置。这个位置是centerIndex - maxLen 1如果centerIndex - maxLen是‘#’。那么原串中的中心下标就是( (centerIndex - maxLen 1) - 1 ) / 2 (centerIndex - maxLen) / 2。长度就是maxLen因为t中半径maxLen对应原串中回文串的半径长度。所以原串中最长回文子串的起始索引是(centerIndex - maxLen) / 2长度是maxLen。问题2算法初始化或边界条件导致错误。预处理首尾添加‘^’和‘$’等不会出现的字符是为了让循环while (t[i 1 p[i]] t[i - 1 - p[i]])无需检查下标越界因为遇到边界字符必然不相等循环会自动停止。循环变量for (int i 1; i len - 1; i)从1开始到len-2结束正好跳过了首尾的边界字符。问题3计算回文子串个数时公式用错。安全做法不要死记公式。遍历p数组对于每个中心i如果t[i]是‘#’即i为偶数它代表原串中两个字符之间的空隙。以它为中心的回文串长度是偶数。它能贡献的回文子串数量是p[i] / 2。如果t[i]是字符即i为奇数它代表原串中的一个字符。以它为中心的回文串长度是奇数。它能贡献的回文子串数量是(p[i] 1) / 2。 将所有的贡献累加即可。这样思考更清晰不易出错。6. 性能对比与算法选择策略了解了三种算法在实际问题中该如何选择呢这里做一个简单的对比。特性KMP算法扩展KMP (Z算法)Manacher算法核心用途单模式串匹配字符串所有后缀与自身的匹配/双串匹配寻找最长回文子串/所有回文子串时间复杂度O(nm)O(nm)O(n)空间复杂度O(m)O(nm)O(n)预处理对象模式串P通常处理单个字符串S或P#T原串S插入分隔符后优势匹配过程主串指针不回溯高效稳定。next数组思想应用广泛。一次性获得所有后缀的匹配信息解决某些问题更直接。解决回文问题的线性时间复杂度最优算法。局限主要解决匹配问题功能相对单一。理解和实现比KMP稍复杂应用场景相对专一。专用于回文问题通用性不如前两者。选择建议当问题明确是单模式串匹配或需要利用前缀函数如周期判断、最短回文串时首选。当需要全局性的匹配信息如所有匹配位置、字符串周期时使用。也常用于双串匹配问题。任何需要高效处理回文子串最长、全部、计数的问题无脑选择Manacher。个人经验在竞赛或面试中KMP和Manacher是必须掌握的“硬通货”。KMP的next数组思想经常被变形后用于其他DP或字符串问题。Manacher是回文问题的标准答案。扩展KMP可以作为你的“秘密武器”在一些特定场景下写出更简洁高效的代码。平时练习时建议对同一道题尝试用不同算法解决比如“找出所有匹配位置”既可以用KMP也可以用扩展KMP对比一下代码和思维过程对理解它们的内在联系大有裨益。最后再分享一个调试字符串算法的小技巧不要只用复杂的大样例。准备几个短小但有代表性的测试用例比如空字符串。单字符字符串。全部相同字符的字符串如“aaaa”。具有明显周期或对称性的字符串如“ababab”,“abcba”。 用这些例子手动模拟算法过程或者让程序打印出关键数组next、z、p与手算结果对比能快速定位绝大多数逻辑错误。字符串算法就像一把精致的瑞士军刀理解其原理掌握其细节多加练习你就能在解决问题的道路上从容地选择最合适的那一把。 KMP、扩展KMP与Manacher：三大字符串算法核心原理与实战详解
1. 项目概述从“暴力”到“优雅”的字符串匹配进化之路如果你刷过一些算法题尤其是在处理字符串相关的问题时一定对“超时”这两个字深恶痛绝。一个看似简单的模式匹配用最直观的双重循环去写在小数据量下跑得飞快一旦数据规模上去立刻给你一个无情的“TLE”Time Limit Exceeded。我刚开始接触算法时就无数次栽在这个坑里。后来才知道字符串匹配这片江湖早已不是“暴力匹配”一家独大的天下了。三位“高手”——KMP、扩展KMP和Manacher各自掌握着独门绝技能让你在面对诸如“寻找子串”、“最长回文子串”这类问题时从“苦苦挣扎”变得“游刃有余”。“kuangbin带你飞”这个专题计划在算法竞赛圈子里可以说是无人不知。它就像一份精心编排的武功秘籍把各个算法知识点分门别类带着学习者一路打怪升级。专题十六聚焦的正是字符串处理中这三个核心且经典的算法。KMP解决的是高效的单模式串匹配问题它教会我们如何利用已经匹配的信息避免主串指针的回退实现线性的时间复杂度。扩展KMP则可以看作是KMP思想的延伸它不仅能解决匹配问题还能一次性求出主串所有后缀与模式串的最长公共前缀在处理某些复杂问题时非常有用。而Manacher算法则是专门为“寻找最长回文子串”这个问题而生的“神器”它用巧妙的中心扩展和对称性将这个问题的时间复杂度也降到了线性。掌握这三个算法绝不仅仅是为了通过几道算法题。它们背后蕴含的“利用已有信息避免重复计算”的思想是优化算法、提升程序效率的核心思维。无论是文本编辑器的查找功能、生物信息学的基因序列比对还是网络协议中的数据包解析都能看到这些算法思想的影子。接下来我就结合自己刷题和教学的经验把这三种算法的核心原理、实现细节以及那些容易踩的坑掰开揉碎了讲给你听。2. 核心算法原理深度拆解理解“为什么”比记住“怎么做”更重要很多人在学习这些算法时容易陷入一个误区死记硬背模板代码。结果就是题目稍微一变或者需要自己推导关键数组时就束手无策了。我们必须从原理层面理解它们明白每一个步骤背后的意图才能做到举一反三。2.1 KMP算法失配时模式串该滑多远KMP算法的核心在于一个叫做next数组有些资料称为prefix table或部分匹配表的东西。它解决了暴力匹配中最大的浪费当主串S[i]和模式串P[j]失配时暴力匹配会将i回溯j归零重新开始。而KMP算法发现i完全不需要回溯只需要将j移动到某个位置next[j]即可。next数组的定义对于模式串Pnext[j]的值是P[0...j-1]这个子串中最长的、相等的前缀和后缀的长度。前缀指除了最后一个字符以外字符串的全部头部组合。后缀指除了第一个字符以外字符串的全部尾部组合。举个例子模式串P “ababc”当j4(指向字符‘c’)我们看P[0...3]即“abab”。它的前缀有“a”,“ab”,“aba”。它的后缀有“b”,“ab”,“bab”。共同的前缀和后缀是“ab”长度为2。所以next[4] 2。这个值的意义是什么它意味着在位置j失配时P[0...next[j]-1]这段前缀已经和主串中对应位置的字符匹配成功了。所以我们可以直接把模式串的j指针移动到next[j]让这段已经匹配好的前缀对齐主串然后从P[next[j]]开始继续比较。主串的指针i完全不动。计算next数组的过程本身就是一个“模式串自我匹配”的过程是理解KMP的关键。我们可以用两个指针i和j其中i指向当前待计算next值的位置后缀的末尾j指向前缀的末尾同时也是next值。初始化next[0] -1(或0取决于实现习惯-1的写法更通用)i 0, j -1。如果j -1或P[i] P[j]则next[i] j。这表示匹配成功最长公共前后缀长度增加。如果P[i] ! P[j]则令j next[j]。这一步是精髓它利用已经计算好的next值进行回溯寻找更短的、可能匹配的前缀。注意next数组的计算是KMP中最容易出错的部分。一定要理解j next[j]这个操作它和主匹配过程中的操作是完全同构的都是在失配时利用已知信息跳转。2.2 扩展KMP算法一次性看清所有后缀的“亲戚关系”扩展KMPZ-algorithm要解决的问题略有不同给定一个字符串S求出S的每一个后缀与S本身的最长公共前缀LCP长度这个长度数组通常记为Z[i]。其中Z[0]通常定义为0或n长度。这个算法同样是线性时间复杂度其核心思想是维护一个“匹配箱”或称“Z-box”[L, R]这个区间代表了当前已知的、与前缀匹配的最右端的一个子串。L和R记录了这个匹配子串的左右边界。对于当前位置i如果i R说明当前位置在已知匹配箱之外我们只能用最朴素的暴力方法逐个字符比较计算Z[i]然后更新L和R。如果i R说明i在已知匹配箱内。那么S[i...R]这段是S[0...R-L]的复制。我们可以利用已经计算好的Z[i-L]来快速推断Z[i]的初始值。但要注意一个边界推断出的长度不能超过R-i1超过的部分仍需暴力检查。扩展KMP可以用来高效解决很多问题比如寻找字符串的所有匹配位置通过计算模式串P‘#’主串S的Z数组、寻找字符串的最小周期等。它提供了一种全局的“自我相似性”视图。2.3 Manacher算法巧用对称一击即中的回文判官寻找一个字符串中的最长回文子串最直观的方法是枚举所有中心点向两边扩展中心扩展法。但这样时间复杂度是O(n²)。Manacher算法的妙处在于它通过插入分隔符如‘#’将奇偶长度的回文统一为奇数长度处理并利用回文串的对称性避免了大量重复的扩展计算。算法的核心是维护一个回文半径数组p[i]以及当前能延伸到最右端的回文中心C和其右边界R。p[i]表示以i为中心处理后的新串T中的最长回文半径包含中心点。C和R表示当前所有回文子串中右边界最靠右的那个回文子串的中心和右边界。关键推导当我们要计算p[i]时如果i R无法利用对称性只能从1开始中心扩展。如果i R那么i关于中心C的对称点是j 2*C - i。我们可以利用p[j]来快速获得p[i]的一个下限。如果p[j]对应的回文串左边界在C的回文串左边界之内即j - p[j] 1 2*C - R那么根据对称性p[i]至少等于p[j]。如果p[j]对应的回文串左边界超出了C的回文串左边界那么p[i]至少等于R - i 1。综合起来p[i]的初始值就是min(p[j], R - i 1)。在得到初始半径后再尝试向两边扩展并更新C和R。这个算法的精妙之处在于大部分情况下步骤2直接给出了p[i]的最终值无需扩展。只有当下限值刚好触达边界R时才需要继续扩展探索。这保证了算法是线性的。3. 算法实现与代码细节从理论到落地的关键一步理解了原理我们来看看如何用代码实现。这里我以C为例因为这是算法竞赛中最常用的语言但逻辑是通用的。3.1 KMP算法的标准实现与next数组优化首先实现计算next数组的函数。这里采用next[0] -1的版本它在编码时逻辑更清晰。// 计算模式串p的next数组 void getNext(const string p, vectorint next) { int n p.size(); next.resize(n); next[0] -1; int i 0, j -1; while (i n - 1) { // 注意循环条件计算到next[n-1]即可 if (j -1 || p[i] p[j]) { i; j; // 标准next数组 next[i] j; // 优化版next数组有时称为nextval // if (p[i] ! p[j]) next[i] j; // else next[i] next[j]; } else { j next[j]; } } }实操心得while (i n - 1)这个条件需要特别注意。因为我们在循环体内是先i; j;再赋值所以i最大会被增加到n-1恰好计算出next[n-1]。如果写成i n则会越界。接下来是KMP匹配的主函数// KMP匹配返回所有匹配起始位置 vectorint kmpSearch(const string s, const string p) { vectorint next; getNext(p, next); vectorint res; int i 0, j 0; // i主串指针j模式串指针 int n s.size(), m p.size(); while (i n) { if (j -1 || s[i] p[j]) { i; j; } else { j next[j]; } if (j m) { // 完全匹配 res.push_back(i - j); // 记录匹配起始位置 j next[j]; // 继续寻找下一个匹配注意这里jmnext[m]需要预先计算或理解为0 } } return res; }关于next数组的优化标准next数组在某些情况下仍有小优化空间。例如模式串“aaaaab”在j4字符‘a’失配时next[4]3跳转后还是‘a’必然继续失配会连续跳转多次。优化版常叫nextval在计算next[i]时如果发现p[i] p[j]则直接让next[i] next[j]一步跳转到最终可能匹配的位置。这在模式串字符重复度高时能提升常数时间性能。3.2 扩展KMPZ算法的实现模板扩展KMP的实现需要仔细处理边界特别是“匹配箱”的维护。// 计算字符串s的Z数组 vectorint getZArray(const string s) { int n s.size(); vectorint z(n, 0); int l 0, r 0; // [l, r]是最右匹配箱 for (int i 1; i n; i) { if (i r) { // i在匹配箱内可以利用对称性 z[i] min(z[i - l], r - i 1); } // 暴力扩展注意边界 while (i z[i] n s[z[i]] s[i z[i]]) { z[i]; } // 更新最右匹配箱 if (i z[i] - 1 r) { l i; r i z[i] - 1; } } // 通常z[0]定义为0或n这里我们按算法逻辑保持0有时题目要求设为n // z[0] n; // 根据需求决定 return z; }一个经典应用寻找文本T中所有模式串P的出现位置。我们可以构造新字符串S P ‘#’ T然后计算S的Z数组。对于T部分即i m的位置其中m是P的长度如果Z[i] m那么就找到了一个匹配起始位置是i - m - 1。3.3 Manacher算法的实现与回文复原Manacher的实现需要先对原字符串进行预处理插入分隔符。// 预处理将原字符串s转换为包含分隔符的新字符串t string preProcess(const string s) { int n s.size(); if (n 0) return ^$; // 边界处理 string t ^; for (int i 0; i n; i) { t #; t s[i]; } t #$; return t; } // Manacher算法主体返回最长回文子串的长度 int manacher(const string s) { string t preProcess(s); int len t.size(); vectorint p(len, 0); int C 0, R 0; // 中心与右边界 int maxLen 0; // 记录最长半径 for (int i 1; i len - 1; i) { // 跳过首尾的‘^’和‘$’ int i_mirror 2 * C - i; // 计算i关于C的对称点 // 利用对称性初始化p[i] if (R i) { p[i] min(R - i, p[i_mirror]); } else { p[i] 0; } // 中心扩展 while (t[i 1 p[i]] t[i - 1 - p[i]]) { p[i]; } // 更新最右回文串中心C和边界R if (i p[i] R) { C i; R i p[i]; } // 更新最大回文半径 maxLen max(maxLen, p[i]); } // 在原串s中最长回文子串的长度等于maxLen return maxLen; }如果需要输出最长回文子串本身可以在更新maxLen时记录中心点centerIndex i。算法结束后根据centerIndex和maxLen可以反向映射回原字符串s截取出子串。映射关系是原串中的中心位置为(centerIndex - maxLen - 1) / 2长度为maxLen。4. 典型应用场景与题目实战解析懂了原理和代码我们得知道它们能用来干什么。下面结合LeetCode和ACM的经典题目看看如何运用这三个算法。4.1 KMP的实战不仅仅是匹配题目1实现 strStr() (LeetCode 28)这是KMP最直接的应用。直接套用上面的kmpSearch函数找到第一个匹配位置返回即可。这道题是检验KMP实现正确性的试金石。题目2重复的子字符串 (LeetCode 459)判断一个字符串是否可以由它的一个子串重复多次构成。一个巧妙的解法利用了KMP的next数组。假设字符串s长度为n计算其next数组。如果next[n] 0且n % (n - next[n]) 0那么字符串就是由长度为n - next[n]的子串重复构成的。原理n - next[n]就是最小重复单元的长度。如果整个字符串能被这个长度整除说明它是重复的。题目3最短回文串 (LeetCode 214)给定一个字符串s你可以在它的前面添加字符使其成为回文串。找到最短的回文串。一个高效解法是构造字符串t s ‘#’ reverse(s)然后计算t的KMP next数组。next[t.length()]的值就是s的前缀中与s的后缀匹配的最长长度。那么我们需要补充的字符就是s中剩余部分的反转。4.2 扩展KMP的实战全局视角下的匹配题目查找字符串中所有出现位置如前所述构造P#T求Z数组是比KMP更直观的解法。KMP需要两个阶段求next和匹配而Z算法一步到位得到所有信息。题目字符串的周期对于一个字符串s如果存在一个字符串t使得s是t重复多次的前缀那么t就是s的一个周期。利用Z数组我们可以轻松找到所有可能的周期长度。对于长度len如果len能整除n且Z[len] n - len那么len就是一个周期长度。这比用KMP的next数组判断更直观。4.3 Manacher的实战回文问题的“终结者”题目1最长回文子串 (LeetCode 5)这是Manacher算法的招牌题目。直接用上面的模板在更新maxLen时记录下中心点centerIndex最后根据映射关系从原字符串中提取子串即可。时间复杂度O(n)远优于中心扩展法的O(n²)。题目2回文子串的个数 (LeetCode 647)计算一个字符串中有多少个回文子串。用Manacher算法求出每个位置i的回文半径p[i]后对于处理后的字符串T以T[i]为中心的回文串数量在原串中就是(p[i] 1) / 2。解释在T中回文半径p[i]包含了分隔符‘#’。以i为中心长度为1, 3, 5, ..., p[i]的回文串都是有效的对应原串中长度为0, 1, 2, ...的回文串。但我们需要的是原串中的回文串且原串中回文串中心可能在字符上也可能在字符间对应T中的字符位和‘#’位。一个简单的结论是将T中每个中心点求得的p[i]相加后除以2就是原串中所有回文子串的个数。更稳妥的做法是遍历p数组对每个p[i]累加p[i] / 2如果T[i]是‘#’对应原串偶数长度回文或(p[i] 1) / 2如果T[i]是字符对应原串奇数长度回文。题目3分割回文串 II (LeetCode 132)给定一个字符串s将s分割成一些子串使每个子串都是回文串。返回符合要求的最少分割次数。这是一个动态规划问题。我们可以先用Manacher算法或者普通的中心扩展法预处理出一个二维布尔数组isPal[i][j]表示s[i...j]是否是回文串。然后进行DPdp[i]表示s[0...i]的最小分割次数。状态转移方程为如果s[0...i]整体是回文dp[i]0否则dp[i] min(dp[j] 1)其中j i且s[j1...i]是回文。预处理回文信息时Manacher算法能提供O(n²)的预处理信息通过每个中心扩展但更常见的做法是用中心扩展法O(n²)预处理因为DP本身也是O(n²)。Manacher在这里的优势是常数更小。5. 常见“坑点”与调试技巧实录即使理解了算法实现时也难免出错。下面是我和学生们常遇到的一些问题。5.1 KMP算法常见问题问题1next数组计算死循环或越界。原因循环条件或指针更新顺序错误。特别是在j next[j]这一步如果next[j]计算错误比如为负或等于自身可能导致无限循环。排查用一个小例子如“abab”手动模拟打印出每一步的i, j, next[i]值。确保在p[i]p[j]时是先i, j再赋值next[i]j。问题2匹配时漏掉重叠的匹配。原因找到一个完全匹配j m后j的回退位置不对。如果直接j0会漏掉像主串“aaaaa”中找模式串“aa”这种重叠匹配。解决找到匹配后执行j next[j]。这就要求我们的next数组长度至少为m1即需要计算出next[m]的值。在getNext函数中循环条件应为i m或i m但最后额外处理一次确保next[m]被正确计算。问题3优化版nextval数组理解错误。现象使用了优化版nextval后匹配结果反而错了。分析优化版是在计算next数组的过程中进行的优化而不是先算出标准next再转换。代码中的注释部分展示了两种写法。务必理解优化逻辑是如果p[i] p[j]那么next[i]应该直接等于next[j]因为即使跳转到j由于字符相同依然会失配不如一步到位。5.2 扩展KMP算法常见问题问题1Z数组计算错误特别是边界r的更新。关键点z[i] min(z[i - l], r - i 1);这一行是核心。i-l是对称点z[i-l]是对称点的已知匹配长度。但这个长度不能超过当前匹配箱的右边界r否则超出的部分我们尚未验证所以要用min。调试在循环内打印i, l, r, z[i]的值对照一个简单字符串如“aabcaabx”的Z数组正确值一步步检查。问题2处理“P#T”结构时索引映射混乱。技巧明确新字符串S的长度是m 1 n。S[0...m-1]是PS[m]是分隔符‘#’S[m1...mn]是T。计算Z数组后对于i在[m1, mn]区间如果Z[i] m则T中的匹配起始位置是(i - (m1)) - m不对应该是i - (m1)是T中对应字符的索引但匹配是从这个索引往前推m个字符吗仔细想当Z[i] m时意味着从S[i]开始的m个字符和S[0...m-1]即P匹配。S[i]对应T中的位置是i - (m1)。所以匹配在T中的起始位置就是i - (m1)。不需要再减m因为Z[i]表示的是从i开始匹配的长度。5.3 Manacher算法常见问题问题1预处理字符串后回文半径到原字符串的映射搞错。牢记公式设原串s预处理后串tt中下标为i的字符非‘#’对应原串下标为(i-1)/2。最长回文子串在原串中的中心位置为(centerIndex - 1 - maxLen) / 2我们来推导在t中回文串实际覆盖的字符范围是[centerIndex - maxLen, centerIndex maxLen]。这个范围内的‘#’和字符交替。原串中的回文串起始位置对应t中第一个非‘#’字符的位置。这个位置是centerIndex - maxLen 1如果centerIndex - maxLen是‘#’。那么原串中的中心下标就是( (centerIndex - maxLen 1) - 1 ) / 2 (centerIndex - maxLen) / 2。长度就是maxLen因为t中半径maxLen对应原串中回文串的半径长度。所以原串中最长回文子串的起始索引是(centerIndex - maxLen) / 2长度是maxLen。问题2算法初始化或边界条件导致错误。预处理首尾添加‘^’和‘$’等不会出现的字符是为了让循环while (t[i 1 p[i]] t[i - 1 - p[i]])无需检查下标越界因为遇到边界字符必然不相等循环会自动停止。循环变量for (int i 1; i len - 1; i)从1开始到len-2结束正好跳过了首尾的边界字符。问题3计算回文子串个数时公式用错。安全做法不要死记公式。遍历p数组对于每个中心i如果t[i]是‘#’即i为偶数它代表原串中两个字符之间的空隙。以它为中心的回文串长度是偶数。它能贡献的回文子串数量是p[i] / 2。如果t[i]是字符即i为奇数它代表原串中的一个字符。以它为中心的回文串长度是奇数。它能贡献的回文子串数量是(p[i] 1) / 2。 将所有的贡献累加即可。这样思考更清晰不易出错。6. 性能对比与算法选择策略了解了三种算法在实际问题中该如何选择呢这里做一个简单的对比。特性KMP算法扩展KMP (Z算法)Manacher算法核心用途单模式串匹配字符串所有后缀与自身的匹配/双串匹配寻找最长回文子串/所有回文子串时间复杂度O(nm)O(nm)O(n)空间复杂度O(m)O(nm)O(n)预处理对象模式串P通常处理单个字符串S或P#T原串S插入分隔符后优势匹配过程主串指针不回溯高效稳定。next数组思想应用广泛。一次性获得所有后缀的匹配信息解决某些问题更直接。解决回文问题的线性时间复杂度最优算法。局限主要解决匹配问题功能相对单一。理解和实现比KMP稍复杂应用场景相对专一。专用于回文问题通用性不如前两者。选择建议当问题明确是单模式串匹配或需要利用前缀函数如周期判断、最短回文串时首选。当需要全局性的匹配信息如所有匹配位置、字符串周期时使用。也常用于双串匹配问题。任何需要高效处理回文子串最长、全部、计数的问题无脑选择Manacher。个人经验在竞赛或面试中KMP和Manacher是必须掌握的“硬通货”。KMP的next数组思想经常被变形后用于其他DP或字符串问题。Manacher是回文问题的标准答案。扩展KMP可以作为你的“秘密武器”在一些特定场景下写出更简洁高效的代码。平时练习时建议对同一道题尝试用不同算法解决比如“找出所有匹配位置”既可以用KMP也可以用扩展KMP对比一下代码和思维过程对理解它们的内在联系大有裨益。最后再分享一个调试字符串算法的小技巧不要只用复杂的大样例。准备几个短小但有代表性的测试用例比如空字符串。单字符字符串。全部相同字符的字符串如“aaaa”。具有明显周期或对称性的字符串如“ababab”,“abcba”。 用这些例子手动模拟算法过程或者让程序打印出关键数组next、z、p与手算结果对比能快速定位绝大多数逻辑错误。字符串算法就像一把精致的瑞士军刀理解其原理掌握其细节多加练习你就能在解决问题的道路上从容地选择最合适的那一把。