1. 项目概述从“暴力”到“优雅”的字符串匹配进化之路在算法竞赛和日常开发中字符串处理是绕不开的坎。无论是搜索引擎的关键词匹配、文本编辑器的查找替换还是生物信息学中的基因序列比对其核心都离不开高效的字符串匹配算法。很多朋友初学时会用最朴素的“暴力匹配”Brute-Force即一个字符一个字符地滑动比较其时间复杂度高达 O(n*m)数据量稍大就力不从心。这时我们急需更高效的武器。这正是“kuangbin带你飞”专题十六聚焦的核心KMP、扩展KMP与Manacher算法。这三个算法堪称解决字符串匹配与回文问题的“三剑客”能将许多看似复杂的问题从平方级复杂度优化到线性级。简单来说这个专题的目标是带你彻底掌握这三种算法的思想、实现与应用。KMP解决的是单模式串匹配问题扩展KMP处理的是所有后缀与模式串的最长公共前缀而Manacher则专门用于寻找字符串中的最长回文子串。理解它们不仅能让你在比赛中快速AC相关题目更能深刻体会到“利用已知信息避免重复比较”这一核心的算法优化思想。无论你是正在备战ACM/ICPC、蓝桥杯的选手还是希望夯实算法基础的开发者这个专题都是你字符串算法能力进阶的必经之路。2. 核心算法思想与原理深度拆解2.1 KMP算法失配不是从头再来的理由KMP算法的全称是Knuth-Morris-Pratt算法由三位计算机科学家共同提出。它的核心魅力在于当主串与模式串在某一位匹配失败时它不是简单地将模式串向后滑动一位从头比较而是利用已经匹配成功的那部分信息将模式串滑动到一个“有意义”的位置继续比较。2.1.1 Next数组算法的灵魂所在KMP高效的关键在于一个叫做next的数组有些实现也称为fail或prefix数组。对于模式串Pnext[i]表示子串P[0...i]中最长的、相等的真前缀与真后缀的长度。真前缀/真后缀指不包括字符串本身的前缀/后缀。例如字符串abab其真前缀有a,ab,aba真后缀有b,ab,bab。其中最长的相等真前缀和真后缀是ab长度为2。为什么需要这个设想我们在主串S中匹配模式串P当匹配到S[i]和P[j]失败时在暴力算法中i会回溯j归零。但KMP发现既然S[i-j...i-1]已经和P[0...j-1]匹配成功了而P[0...next[j-1]]又等于P[j-next[j-1]...j-1]那么我们就可以直接把P的开头对齐到i-next[j-1]的位置让j变成next[j-1]然后继续比较S[i]和P[j]。这样主串的指针i就永不回溯从而实现了 O(n) 的匹配效率。next数组的构建过程以模式串P ababc为例next[0] 0。单个字符没有真前缀和真后缀。对于i1子串ab真前缀a真后缀b不相等next[1]0。对于i2子串aba真前缀有a,ab真后缀有a,ba。相等的只有a长度为1next[2]1。对于i3子串abab真前缀有a,ab,aba真后缀有b,ab,bab。相等的最长的是ab长度为2next[3]2。对于i4子串ababc真前缀有a,ab,aba,abab真后缀有c,bc,abc,babc。没有相等的next[4]0。所以next数组为[0, 0, 1, 2, 0]。2.1.2 匹配过程的动态推演假设主串S abababc模式串P ababcnext数组已知。初始化i0主串指针j0模式串指针。S[0]a匹配P[0]ai1, j1。S[1]b匹配P[1]bi2, j2。S[2]a匹配P[2]ai3, j3。S[3]b匹配P[3]bi4, j4。S[4]a与P[4]c失配。此时j4查next[j-1] next[3] 2。将j更新为2。这意味着模式串的前两位ab已经和主串的S[2...3]也是ab匹配好了我们直接从P[2]即a开始与S[4]即a比较。S[4]a匹配P[2]ai5, j3。S[5]b匹配P[3]bi6, j4。S[6]c匹配P[4]c匹配成功。可以看到主串指针i从0走到6只遍历了一次没有回溯。2.2 扩展KMPZ-Algorithm全方位的前缀匹配侦查扩展KMPZ-Algorithm要解决的问题是给定两个字符串S和P求出S的每一个后缀与P的最长公共前缀的长度。这个结果通常存储在一个Z数组或extend数组中。2.2.1 Z数组的定义与核心思想对于字符串str我们定义Z[i]为str[i...]即以i开头的后缀与str本身即整个字符串的最长公共前缀长度。扩展KMP求S的每个后缀与P的LCP其巧妙之处在于它构造了一个新的字符串P ‘#’ S然后对这个新字符串计算Z数组。‘#’是一个不出现在P和S中的分隔符用于防止越界匹配。算法的核心是维护一个“匹配窗口”[L, R]表示当前已知的、与P匹配的最靠右的区间。当我们计算Z[i]时如果i R说明当前位置在已知窗口外只能老老实实暴力匹配。如果i R说明i在窗口内。那么S[i...]与P的匹配情况可以参考S[i-L...]与P的匹配情况因为S[L...R]等于P[0...R-L]。我们可以利用已经计算好的Z[i-L]来快速确定一个初始匹配长度k min(Z[i-L], R-i1)然后从这个长度开始继续暴力匹配。2.2.2 算法流程示例设P abab,S bababa构造str abab#bababa。 我们需要计算str的Z数组从索引0开始但最终我们只关心‘#’之后的部分即对应S的每个后缀与P的匹配。手动计算str的Z数组过程略繁体现算法思想Z[0]无定义或为字符串长度。计算Z[5]对应S的第一个字符‘b’时i5 R暴力匹配得到Z[5]0因为‘b’不等于P[0]‘a’。在后续计算中算法会动态更新L和R窗口利用已知信息加速。最终str中‘#’之后部分的Z值[0, 2, 0, 3, 0, 1]就对应了S的每个后缀bababa,ababa,baba,aba,ba,a与Pabab的最长公共前缀长度。2.3 Manacher算法线性时间内的回文“探测器”寻找一个字符串中的最长回文子串暴力解法需要枚举所有子串并判断复杂度 O(n³)中心扩散法优化到 O(n²)。Manacher算法则将其优化到了惊人的 O(n)。2.3.1 预处理与核心概念Manacher算法的第一步是进行一个巧妙的预处理在原始字符串的每个字符之间以及首尾插入一个相同的、不会出现在原串中的分隔符如‘#’。这样无论原串长度是奇是偶新串的长度都变为奇数2*n1统一了奇偶回文中心的情况。例如aba-“#a#b#a#”abba-“#a#b#b#a#”。我们定义一个新数组p[i]表示以新串中第i个字符为中心的最长回文半径包含中心点。那么p[i] - 1就是原串中以该位置为中心的回文串的长度。2.3.2 利用对称性加速算法的精髓在于维护一个当前探索到的最右回文边界R以及其对应的回文中心C。当我们计算p[i]时如果i R无法利用对称性只能中心扩散。如果i R那么i关于中心C的对称点是i_mirror 2*C - i。我们可以利用p[i_mirror]的信息。如果p[i_mirror] R - i说明以i_mirror为中心的回文完全落在以C为中心的大回文内根据对称性p[i] p[i_mirror]。如果p[i_mirror] R - i说明以i_mirror为中心的回文左臂可能触及或超过了大回文的左边界。我们只能确保p[i]至少为R - i然后需要继续向两边扩散检查以确定是否能扩展得更远。每次扩散或检查后如果i p[i] R就更新C i和R i p[i]。2.3.3 算法执行过程速览以原串cbbd为例预处理后为“#c#b#b#d#”。初始化C0, R0。i0: 中心为‘#’p[0]1更新R1。i1: 对称点i_mirror-1无效中心扩散得p[1]2“#c#”更新C1, R3。i2:iRi_mirror0p[i_mirror]1R-i1所以p[2]至少为1。检查发现可以扩展到“#b#”p[2]2。ip[i]4 R更新C2, R4。i3:iRi_mirror1p[i_mirror]2R-i1所以p[3]至少为min(2,1)1。检查发现无法扩展p[3]1。以此类推... 最终最大的p[i]是2对应中心‘#’或‘b’原串最长回文子串长度为2-11。实际上“bb”是长度为2的回文子串这需要检查以字符为中心的情况。在“#c#b#b#d#”中i5对应第二个‘b’后面的‘#’的p[5]33-12即原串中的“bb”。3. 算法实现细节与代码模板3.1 KMP算法的标准实现与优化KMP的实现分为两部分构建next数组和使用next数组进行匹配。3.1.1 Next数组的构建代码Cvectorint getNext(string p) { int n p.size(); vectorint next(n, 0); for (int i 1, j 0; i n; i) { // 当不匹配时利用next数组回退j while (j 0 p[i] ! p[j]) { j next[j - 1]; } // 如果匹配j和i同时后移 if (p[i] p[j]) { j; } // 记录next[i]的值 next[i] j; } return next; }关键点解析j有两个含义1) 当前匹配的前缀长度2) 指向模式串中将要比较的字符。while循环是精髓当p[i] ! p[j]时j需要回退到next[j-1]的位置继续尝试匹配。这模拟了在模式串自身中寻找更短的相同前后缀的过程。if语句处理匹配成功的情况j加1。next[i]被赋值为j即当前位置之前子串的最长相等前后缀长度。3.1.2 基于Next数组的匹配代码int kmpSearch(string s, string p) { vectorint next getNext(p); int count 0; // 记录匹配次数 for (int i 0, j 0; i s.size(); i) { // 失配时j回退 while (j 0 s[i] ! p[j]) { j next[j - 1]; } // 匹配时j前进 if (s[i] p[j]) { j; } // 完全匹配 if (j p.size()) { count; // 找到一个匹配位置是 i - j 1 // 寻找下一个可能匹配j回退 j next[j - 1]; } } return count; }注意事项匹配过程的代码结构与构建next数组惊人地相似这是因为两者的核心思想一致利用已知信息避免回溯。找到完全匹配后j next[j-1]这一步非常重要它允许我们找到所有可能的重叠匹配。例如在“ababab”中找“abab”除了在索引0处匹配在索引2处也有重叠匹配。3.2 扩展KMPZ-Algorithm的实现模板vectorint getZ(string str) { int n str.size(); vectorint z(n, 0); int l 0, r 0; // [l, r] 是最右匹配区间 for (int i 1; i n; i) { if (i r) { z[i] min(z[i - l], r - i 1); } // 暴力扩展注意边界 while (i z[i] n str[z[i]] str[i z[i]]) { z[i]; } // 更新最右匹配区间 if (i z[i] - 1 r) { l i; r i z[i] - 1; } } // z[0] 通常定义为0或n根据问题需要调整 return z; } // 计算字符串S的每个后缀与模式串P的最长公共前缀 vectorint exKMP(string s, string p) { string combine p # s; vectorint z getZ(combine); vectorint extend(s.size(), 0); // combine中‘#’之后的部分对应s其z值就是extend值 for (int i 0; i s.size(); i) { extend[i] z[p.size() 1 i]; } return extend; }代码要点l和r维护了当前已知的、与字符串前缀匹配的最靠右的区间[l, r]且str[l...r] str[0...r-l]。if (i r)分支利用了对称性进行快速赋值这是算法达到线性的关键。while循环进行暴力扩展直到不匹配为止。最后更新l和r确保r始终是当前探索到的最右边界。3.3 Manacher算法的实现模板string preProcess(string s) { string t #; for (char c : s) { t c; t #; } return t; } int manacher(string s) { string t preProcess(s); int n t.size(); vectorint p(n, 0); int C 0, R 0; // 中心最右边界 int maxLen 0; // 记录最长半径 int centerIdx 0;// 记录最长回文中心 for (int i 0; i n; i) { int i_mirror 2 * C - i; // 核心赋值 if (i R) { p[i] min(R - i, p[i_mirror]); } else { p[i] 0; } // 中心扩散 int left i - p[i] - 1; int right i p[i] 1; while (left 0 right n t[left] t[right]) { p[i]; left--; right; } // 更新最右边界和中心 if (i p[i] R) { C i; R i p[i]; } // 更新答案 if (p[i] maxLen) { maxLen p[i]; centerIdx i; } } // 计算原串中的起始位置和长度 int start (centerIdx - maxLen) / 2; int length maxLen; // 因为p[i]是半径对应原串长度就是maxLen // 例如t中回文“#a#b#a#”半径p3原串“aba”长度3 return length; }实现细节与陷阱预处理分隔符的选择很重要必须确保是原串中不出现的字符。p[i]的初始赋值p[i] min(R - i, p[i_mirror])是算法的核心优化。它决定了我们无需从0开始扩散而是从一个更优的起点开始。边界检查在中心扩散的while循环中务必检查left和right的索引是否越界。结果转换最终得到的maxLen就是原串中最长回文子串的长度。起始位置start可以通过(centerIdx - maxLen) / 2计算得到因为预处理字符串中每个原字符前后都有一个‘#’。4. 典型应用场景与题目实战4.1 KMP算法的经典应用场景4.1.1 单模式串匹配这是KMP最基本也是最直接的应用。题目通常直接要求找出模式串在主串中所有出现的位置。例题LeetCode 28. 找出字符串中第一个匹配项的下标。解题思路直接套用KMP模板在匹配过程中当j m模式串长度时记录位置i - m 1即可。4.1.2 循环节问题利用next数组可以高效判断一个字符串是否由某个子串重复多次构成以及计算最小循环节长度。核心原理对于一个长度为n的字符串s如果n % (n - next[n-1]) 0那么该字符串可以由长度为n - next[n-1]的子串重复构成。n - next[n-1]就是最小循环节长度。例题LeetCode 459. 重复的子字符串。实操计算s的next数组检查上述条件。例如“ababab”n6,next[5]4,6 % (6-4) 0所以可以由“ab”重复3次构成。4.1.3 前后缀问题next数组本身记录的就是前缀和后缀的关系因此可以直接用于解决一些前后缀匹配问题。例题给定一个字符串求其所有既是前缀又是后缀的子串的长度。解题从next[n-1]开始不断跳转到next[next[n-1]-1]直到为0这些值就是满足条件的长度。例如“abacabac”next数组末尾值为4对应“abac”再跳转next[3]0所以长度有4和00通常不计。4.2 扩展KMP的应用场景4.2.1 快速计算任意两个后缀的LCP虽然扩展KMP计算的是每个后缀与整个模式串的LCP但通过巧妙构造可以解决更多问题。例如要比较字符串S的两个后缀i和j的LCP可以构造新串S[i...] ‘#’ S然后计算其Z数组Z[n1j-i]就给出了一个上界再结合其他性质可以快速计算。4.2.2 解决特定模式的匹配计数问题有些题目要求统计主串中所有与模式串“近似匹配”或具有特定关系如某个后缀是模式串前缀的子串数量。扩展KMP提供的extend数组能直接给出每个位置开始能匹配多长方便进行统计。例题HDU 4333 Revolving Digits。此题需要比较一个数字循环移位后形成的所有不同数字与原数字的大小关系。可以利用扩展KMP将原串复制一遍接在后面然后计算其每个后缀与原串的LCP从而快速比较。4.3 Manacher算法的应用场景4.3.1 寻找最长回文子串这是Manacher算法的招牌应用可以在O(n)时间内解决。例题LeetCode 5. 最长回文子串。解题直接使用Manacher算法模板在计算p[i]的过程中维护最大值及其中心最后根据中心和半径还原出原串中的子串。4.3.2 统计回文子串总数由于p[i]表示的是以i为中心的最长回文半径在新串中那么以i为中心的回文子串数量就是p[i] / 2向下取整对应原串或(p[i] 1) / 2对应预处理串每个回文中心贡献的奇数长度回文数。遍历所有i求和即可。例题LeetCode 647. 回文子串。技巧无需真正找出每个子串利用p[i]值累加(p[i] 1) / 2即可得到总数。4.3.3 处理基于回文的复杂问题许多动态规划或字符串处理问题如果涉及回文判断使用Manacher预处理出以每个点为中心的最长回文半径可以瞬间将回文判断的复杂度从O(n)降到O(1)从而优化整体算法。例题给定一个字符串求将其分割成若干段使得每一段都是回文串的最小分割次数。思路可以先使用Manacher或动态规划预处理出任意子串[i, j]是否是回文O(n²)或O(n)。然后使用动态规划求解最小分割dp[i]表示前i个字符的最小分割次数dp[i] min(dp[j] 1)其中s[j1...i]是回文。5. 常见疑难问题与性能调优5.1 KMP算法中的Next数组理解误区问题1Next数组的“长度” vs “索引”这是初学者最容易混淆的地方。next[i]表示的是长度即前缀/后缀的字符个数而不是下一个要比较的索引。但在代码中j next[j-1]这个操作next[j-1]作为长度值恰好等于回退后应该指向的新的j的索引值因为字符串索引从0开始。理解这一点对于手动计算和调试代码至关重要。问题2Next数组的优化版本标准的next数组有时可以进行“优化”称为nextVal数组。优化思想是如果回退后的字符和当前字符相同那么这次回退必然还会失配可以继续回退。vectorint getNextVal(string p) { vectorint next getNext(p); vectorint nextVal(p.size(), 0); nextVal[0] 0; for (int i 1; i p.size(); i) { if (p[i] p[next[i]]) { nextVal[i] nextVal[next[i]]; } else { nextVal[i] next[i]; } } return nextVal; }在实际做题中使用标准next数组通常就足够了nextVal优化在模式串重复字符很多时能减少一些不必要的比较但并非必须。5.2 扩展KMP的边界条件与初始化问题Z[0] 的定义在Z-Algorithm中Z[0]通常没有定义或者被定义为整个字符串的长度n因为我们不会将一个字符串与自己后缀的LCP定义为整个字符串。在实现中我们通常从i1开始计算。在解决扩展KMP问题时要特别注意题目对Z[0]的要求避免使用未定义的值。问题分隔符的选择在构造P ‘#’ S时分隔符‘#’必须确保不在P和S的字符集中出现。如果字符集是全体小写字母用‘#’是安全的。如果字符集包含所有可打印字符则需要选择一个如‘$’或‘\0’如果字符串允许等特殊字符。5.3 Manacher算法的实现陷阱陷阱1回文半径p[i]的包含关系p[i]是包含中心点的半径长度。例如对于新串“#a#b#a#”中心b在索引3p[3]4字符串“#a#b#a#”长度7半径4。这意味着回文串是t[3-41 ... 34-1]即t[0...6]。在计算原串起始位置时公式start (centerIdx - maxLen) / 2正是基于此定义推导的。陷阱2整数溢出在计算i_mirror 2 * C - i时虽然通常不会溢出但在一些极端输入或特定语言中需要注意。R和i p[i]也可能超过字符串长度但在循环条件中已被控制。性能调优建议避免频繁的字符串拼接Manacher的预处理步骤如果使用string的操作在循环中可能低效。对于性能要求极高的场景可以预先分配好2*n1的空间然后直接填充字符。使用数组代替vector在确定最大长度后可以使用原生数组int p[2*MAX_N5]来代替vector以减少动态内存分配的开销这在竞赛中有时能带来微小的性能提升。中心扩散的循环展开编译器通常能很好地优化简单的while循环手动展开收益不大。重点应放在算法逻辑的正确性上。5.4 综合问题排查清单当你的KMP/扩展KMP/Manacher代码出现错误时可以按以下清单排查问题现象可能原因检查点KMP匹配结果漏掉或错误1.next数组计算错误。2. 匹配完成后j回退逻辑错误。1. 用简单例子如“abab”手动计算next数组与程序输出对比。2. 检查找到完全匹配后是j 0还是j next[j-1]。后者才能找到重叠匹配。扩展KMP结果全为01. 分隔符选择不当导致匹配越界。2.l,r初始化或更新错误。1. 确保分隔符不在原串中出现。2. 单步调试观察i,l,r,z[i]的变化是否符合算法描述。Manacher结果比实际小1.p[i]的初始赋值min(R-i, p[i_mirror])逻辑错误。2. 中心扩散的循环边界条件错误。1. 确认i_mirror计算正确且i R时才使用快速赋值。2. 检查while循环条件是否为left 0 right n t[left]t[right]。程序运行超时1. 在KMP的while循环或Manacher的扩散循环中陷入死循环。2. 对极大输入使用了低效的字符串操作。1. 确保while循环中有使条件改变的语句如j next[j-1]或p[i]。2. 检查字符串拼接、vector初始化等操作是否在循环内频繁调用。掌握这三个算法意味着你在字符串处理领域拥有了强大的线性时间工具。理解其思想比死记模板更重要。多找一些经典题目练习从暴力解法开始再逐步优化到使用这些高级算法能让你对“优化”二字有更深刻的体会。在“kuangbin带你飞”的专题训练中建议按照由浅入深的顺序刷题先熟练掌握模板再挑战综合性的应用题最终达到灵活运用、融会贯通的境界。
KMP、扩展KMP与Manacher算法：字符串匹配与回文问题的线性优化
1. 项目概述从“暴力”到“优雅”的字符串匹配进化之路在算法竞赛和日常开发中字符串处理是绕不开的坎。无论是搜索引擎的关键词匹配、文本编辑器的查找替换还是生物信息学中的基因序列比对其核心都离不开高效的字符串匹配算法。很多朋友初学时会用最朴素的“暴力匹配”Brute-Force即一个字符一个字符地滑动比较其时间复杂度高达 O(n*m)数据量稍大就力不从心。这时我们急需更高效的武器。这正是“kuangbin带你飞”专题十六聚焦的核心KMP、扩展KMP与Manacher算法。这三个算法堪称解决字符串匹配与回文问题的“三剑客”能将许多看似复杂的问题从平方级复杂度优化到线性级。简单来说这个专题的目标是带你彻底掌握这三种算法的思想、实现与应用。KMP解决的是单模式串匹配问题扩展KMP处理的是所有后缀与模式串的最长公共前缀而Manacher则专门用于寻找字符串中的最长回文子串。理解它们不仅能让你在比赛中快速AC相关题目更能深刻体会到“利用已知信息避免重复比较”这一核心的算法优化思想。无论你是正在备战ACM/ICPC、蓝桥杯的选手还是希望夯实算法基础的开发者这个专题都是你字符串算法能力进阶的必经之路。2. 核心算法思想与原理深度拆解2.1 KMP算法失配不是从头再来的理由KMP算法的全称是Knuth-Morris-Pratt算法由三位计算机科学家共同提出。它的核心魅力在于当主串与模式串在某一位匹配失败时它不是简单地将模式串向后滑动一位从头比较而是利用已经匹配成功的那部分信息将模式串滑动到一个“有意义”的位置继续比较。2.1.1 Next数组算法的灵魂所在KMP高效的关键在于一个叫做next的数组有些实现也称为fail或prefix数组。对于模式串Pnext[i]表示子串P[0...i]中最长的、相等的真前缀与真后缀的长度。真前缀/真后缀指不包括字符串本身的前缀/后缀。例如字符串abab其真前缀有a,ab,aba真后缀有b,ab,bab。其中最长的相等真前缀和真后缀是ab长度为2。为什么需要这个设想我们在主串S中匹配模式串P当匹配到S[i]和P[j]失败时在暴力算法中i会回溯j归零。但KMP发现既然S[i-j...i-1]已经和P[0...j-1]匹配成功了而P[0...next[j-1]]又等于P[j-next[j-1]...j-1]那么我们就可以直接把P的开头对齐到i-next[j-1]的位置让j变成next[j-1]然后继续比较S[i]和P[j]。这样主串的指针i就永不回溯从而实现了 O(n) 的匹配效率。next数组的构建过程以模式串P ababc为例next[0] 0。单个字符没有真前缀和真后缀。对于i1子串ab真前缀a真后缀b不相等next[1]0。对于i2子串aba真前缀有a,ab真后缀有a,ba。相等的只有a长度为1next[2]1。对于i3子串abab真前缀有a,ab,aba真后缀有b,ab,bab。相等的最长的是ab长度为2next[3]2。对于i4子串ababc真前缀有a,ab,aba,abab真后缀有c,bc,abc,babc。没有相等的next[4]0。所以next数组为[0, 0, 1, 2, 0]。2.1.2 匹配过程的动态推演假设主串S abababc模式串P ababcnext数组已知。初始化i0主串指针j0模式串指针。S[0]a匹配P[0]ai1, j1。S[1]b匹配P[1]bi2, j2。S[2]a匹配P[2]ai3, j3。S[3]b匹配P[3]bi4, j4。S[4]a与P[4]c失配。此时j4查next[j-1] next[3] 2。将j更新为2。这意味着模式串的前两位ab已经和主串的S[2...3]也是ab匹配好了我们直接从P[2]即a开始与S[4]即a比较。S[4]a匹配P[2]ai5, j3。S[5]b匹配P[3]bi6, j4。S[6]c匹配P[4]c匹配成功。可以看到主串指针i从0走到6只遍历了一次没有回溯。2.2 扩展KMPZ-Algorithm全方位的前缀匹配侦查扩展KMPZ-Algorithm要解决的问题是给定两个字符串S和P求出S的每一个后缀与P的最长公共前缀的长度。这个结果通常存储在一个Z数组或extend数组中。2.2.1 Z数组的定义与核心思想对于字符串str我们定义Z[i]为str[i...]即以i开头的后缀与str本身即整个字符串的最长公共前缀长度。扩展KMP求S的每个后缀与P的LCP其巧妙之处在于它构造了一个新的字符串P ‘#’ S然后对这个新字符串计算Z数组。‘#’是一个不出现在P和S中的分隔符用于防止越界匹配。算法的核心是维护一个“匹配窗口”[L, R]表示当前已知的、与P匹配的最靠右的区间。当我们计算Z[i]时如果i R说明当前位置在已知窗口外只能老老实实暴力匹配。如果i R说明i在窗口内。那么S[i...]与P的匹配情况可以参考S[i-L...]与P的匹配情况因为S[L...R]等于P[0...R-L]。我们可以利用已经计算好的Z[i-L]来快速确定一个初始匹配长度k min(Z[i-L], R-i1)然后从这个长度开始继续暴力匹配。2.2.2 算法流程示例设P abab,S bababa构造str abab#bababa。 我们需要计算str的Z数组从索引0开始但最终我们只关心‘#’之后的部分即对应S的每个后缀与P的匹配。手动计算str的Z数组过程略繁体现算法思想Z[0]无定义或为字符串长度。计算Z[5]对应S的第一个字符‘b’时i5 R暴力匹配得到Z[5]0因为‘b’不等于P[0]‘a’。在后续计算中算法会动态更新L和R窗口利用已知信息加速。最终str中‘#’之后部分的Z值[0, 2, 0, 3, 0, 1]就对应了S的每个后缀bababa,ababa,baba,aba,ba,a与Pabab的最长公共前缀长度。2.3 Manacher算法线性时间内的回文“探测器”寻找一个字符串中的最长回文子串暴力解法需要枚举所有子串并判断复杂度 O(n³)中心扩散法优化到 O(n²)。Manacher算法则将其优化到了惊人的 O(n)。2.3.1 预处理与核心概念Manacher算法的第一步是进行一个巧妙的预处理在原始字符串的每个字符之间以及首尾插入一个相同的、不会出现在原串中的分隔符如‘#’。这样无论原串长度是奇是偶新串的长度都变为奇数2*n1统一了奇偶回文中心的情况。例如aba-“#a#b#a#”abba-“#a#b#b#a#”。我们定义一个新数组p[i]表示以新串中第i个字符为中心的最长回文半径包含中心点。那么p[i] - 1就是原串中以该位置为中心的回文串的长度。2.3.2 利用对称性加速算法的精髓在于维护一个当前探索到的最右回文边界R以及其对应的回文中心C。当我们计算p[i]时如果i R无法利用对称性只能中心扩散。如果i R那么i关于中心C的对称点是i_mirror 2*C - i。我们可以利用p[i_mirror]的信息。如果p[i_mirror] R - i说明以i_mirror为中心的回文完全落在以C为中心的大回文内根据对称性p[i] p[i_mirror]。如果p[i_mirror] R - i说明以i_mirror为中心的回文左臂可能触及或超过了大回文的左边界。我们只能确保p[i]至少为R - i然后需要继续向两边扩散检查以确定是否能扩展得更远。每次扩散或检查后如果i p[i] R就更新C i和R i p[i]。2.3.3 算法执行过程速览以原串cbbd为例预处理后为“#c#b#b#d#”。初始化C0, R0。i0: 中心为‘#’p[0]1更新R1。i1: 对称点i_mirror-1无效中心扩散得p[1]2“#c#”更新C1, R3。i2:iRi_mirror0p[i_mirror]1R-i1所以p[2]至少为1。检查发现可以扩展到“#b#”p[2]2。ip[i]4 R更新C2, R4。i3:iRi_mirror1p[i_mirror]2R-i1所以p[3]至少为min(2,1)1。检查发现无法扩展p[3]1。以此类推... 最终最大的p[i]是2对应中心‘#’或‘b’原串最长回文子串长度为2-11。实际上“bb”是长度为2的回文子串这需要检查以字符为中心的情况。在“#c#b#b#d#”中i5对应第二个‘b’后面的‘#’的p[5]33-12即原串中的“bb”。3. 算法实现细节与代码模板3.1 KMP算法的标准实现与优化KMP的实现分为两部分构建next数组和使用next数组进行匹配。3.1.1 Next数组的构建代码Cvectorint getNext(string p) { int n p.size(); vectorint next(n, 0); for (int i 1, j 0; i n; i) { // 当不匹配时利用next数组回退j while (j 0 p[i] ! p[j]) { j next[j - 1]; } // 如果匹配j和i同时后移 if (p[i] p[j]) { j; } // 记录next[i]的值 next[i] j; } return next; }关键点解析j有两个含义1) 当前匹配的前缀长度2) 指向模式串中将要比较的字符。while循环是精髓当p[i] ! p[j]时j需要回退到next[j-1]的位置继续尝试匹配。这模拟了在模式串自身中寻找更短的相同前后缀的过程。if语句处理匹配成功的情况j加1。next[i]被赋值为j即当前位置之前子串的最长相等前后缀长度。3.1.2 基于Next数组的匹配代码int kmpSearch(string s, string p) { vectorint next getNext(p); int count 0; // 记录匹配次数 for (int i 0, j 0; i s.size(); i) { // 失配时j回退 while (j 0 s[i] ! p[j]) { j next[j - 1]; } // 匹配时j前进 if (s[i] p[j]) { j; } // 完全匹配 if (j p.size()) { count; // 找到一个匹配位置是 i - j 1 // 寻找下一个可能匹配j回退 j next[j - 1]; } } return count; }注意事项匹配过程的代码结构与构建next数组惊人地相似这是因为两者的核心思想一致利用已知信息避免回溯。找到完全匹配后j next[j-1]这一步非常重要它允许我们找到所有可能的重叠匹配。例如在“ababab”中找“abab”除了在索引0处匹配在索引2处也有重叠匹配。3.2 扩展KMPZ-Algorithm的实现模板vectorint getZ(string str) { int n str.size(); vectorint z(n, 0); int l 0, r 0; // [l, r] 是最右匹配区间 for (int i 1; i n; i) { if (i r) { z[i] min(z[i - l], r - i 1); } // 暴力扩展注意边界 while (i z[i] n str[z[i]] str[i z[i]]) { z[i]; } // 更新最右匹配区间 if (i z[i] - 1 r) { l i; r i z[i] - 1; } } // z[0] 通常定义为0或n根据问题需要调整 return z; } // 计算字符串S的每个后缀与模式串P的最长公共前缀 vectorint exKMP(string s, string p) { string combine p # s; vectorint z getZ(combine); vectorint extend(s.size(), 0); // combine中‘#’之后的部分对应s其z值就是extend值 for (int i 0; i s.size(); i) { extend[i] z[p.size() 1 i]; } return extend; }代码要点l和r维护了当前已知的、与字符串前缀匹配的最靠右的区间[l, r]且str[l...r] str[0...r-l]。if (i r)分支利用了对称性进行快速赋值这是算法达到线性的关键。while循环进行暴力扩展直到不匹配为止。最后更新l和r确保r始终是当前探索到的最右边界。3.3 Manacher算法的实现模板string preProcess(string s) { string t #; for (char c : s) { t c; t #; } return t; } int manacher(string s) { string t preProcess(s); int n t.size(); vectorint p(n, 0); int C 0, R 0; // 中心最右边界 int maxLen 0; // 记录最长半径 int centerIdx 0;// 记录最长回文中心 for (int i 0; i n; i) { int i_mirror 2 * C - i; // 核心赋值 if (i R) { p[i] min(R - i, p[i_mirror]); } else { p[i] 0; } // 中心扩散 int left i - p[i] - 1; int right i p[i] 1; while (left 0 right n t[left] t[right]) { p[i]; left--; right; } // 更新最右边界和中心 if (i p[i] R) { C i; R i p[i]; } // 更新答案 if (p[i] maxLen) { maxLen p[i]; centerIdx i; } } // 计算原串中的起始位置和长度 int start (centerIdx - maxLen) / 2; int length maxLen; // 因为p[i]是半径对应原串长度就是maxLen // 例如t中回文“#a#b#a#”半径p3原串“aba”长度3 return length; }实现细节与陷阱预处理分隔符的选择很重要必须确保是原串中不出现的字符。p[i]的初始赋值p[i] min(R - i, p[i_mirror])是算法的核心优化。它决定了我们无需从0开始扩散而是从一个更优的起点开始。边界检查在中心扩散的while循环中务必检查left和right的索引是否越界。结果转换最终得到的maxLen就是原串中最长回文子串的长度。起始位置start可以通过(centerIdx - maxLen) / 2计算得到因为预处理字符串中每个原字符前后都有一个‘#’。4. 典型应用场景与题目实战4.1 KMP算法的经典应用场景4.1.1 单模式串匹配这是KMP最基本也是最直接的应用。题目通常直接要求找出模式串在主串中所有出现的位置。例题LeetCode 28. 找出字符串中第一个匹配项的下标。解题思路直接套用KMP模板在匹配过程中当j m模式串长度时记录位置i - m 1即可。4.1.2 循环节问题利用next数组可以高效判断一个字符串是否由某个子串重复多次构成以及计算最小循环节长度。核心原理对于一个长度为n的字符串s如果n % (n - next[n-1]) 0那么该字符串可以由长度为n - next[n-1]的子串重复构成。n - next[n-1]就是最小循环节长度。例题LeetCode 459. 重复的子字符串。实操计算s的next数组检查上述条件。例如“ababab”n6,next[5]4,6 % (6-4) 0所以可以由“ab”重复3次构成。4.1.3 前后缀问题next数组本身记录的就是前缀和后缀的关系因此可以直接用于解决一些前后缀匹配问题。例题给定一个字符串求其所有既是前缀又是后缀的子串的长度。解题从next[n-1]开始不断跳转到next[next[n-1]-1]直到为0这些值就是满足条件的长度。例如“abacabac”next数组末尾值为4对应“abac”再跳转next[3]0所以长度有4和00通常不计。4.2 扩展KMP的应用场景4.2.1 快速计算任意两个后缀的LCP虽然扩展KMP计算的是每个后缀与整个模式串的LCP但通过巧妙构造可以解决更多问题。例如要比较字符串S的两个后缀i和j的LCP可以构造新串S[i...] ‘#’ S然后计算其Z数组Z[n1j-i]就给出了一个上界再结合其他性质可以快速计算。4.2.2 解决特定模式的匹配计数问题有些题目要求统计主串中所有与模式串“近似匹配”或具有特定关系如某个后缀是模式串前缀的子串数量。扩展KMP提供的extend数组能直接给出每个位置开始能匹配多长方便进行统计。例题HDU 4333 Revolving Digits。此题需要比较一个数字循环移位后形成的所有不同数字与原数字的大小关系。可以利用扩展KMP将原串复制一遍接在后面然后计算其每个后缀与原串的LCP从而快速比较。4.3 Manacher算法的应用场景4.3.1 寻找最长回文子串这是Manacher算法的招牌应用可以在O(n)时间内解决。例题LeetCode 5. 最长回文子串。解题直接使用Manacher算法模板在计算p[i]的过程中维护最大值及其中心最后根据中心和半径还原出原串中的子串。4.3.2 统计回文子串总数由于p[i]表示的是以i为中心的最长回文半径在新串中那么以i为中心的回文子串数量就是p[i] / 2向下取整对应原串或(p[i] 1) / 2对应预处理串每个回文中心贡献的奇数长度回文数。遍历所有i求和即可。例题LeetCode 647. 回文子串。技巧无需真正找出每个子串利用p[i]值累加(p[i] 1) / 2即可得到总数。4.3.3 处理基于回文的复杂问题许多动态规划或字符串处理问题如果涉及回文判断使用Manacher预处理出以每个点为中心的最长回文半径可以瞬间将回文判断的复杂度从O(n)降到O(1)从而优化整体算法。例题给定一个字符串求将其分割成若干段使得每一段都是回文串的最小分割次数。思路可以先使用Manacher或动态规划预处理出任意子串[i, j]是否是回文O(n²)或O(n)。然后使用动态规划求解最小分割dp[i]表示前i个字符的最小分割次数dp[i] min(dp[j] 1)其中s[j1...i]是回文。5. 常见疑难问题与性能调优5.1 KMP算法中的Next数组理解误区问题1Next数组的“长度” vs “索引”这是初学者最容易混淆的地方。next[i]表示的是长度即前缀/后缀的字符个数而不是下一个要比较的索引。但在代码中j next[j-1]这个操作next[j-1]作为长度值恰好等于回退后应该指向的新的j的索引值因为字符串索引从0开始。理解这一点对于手动计算和调试代码至关重要。问题2Next数组的优化版本标准的next数组有时可以进行“优化”称为nextVal数组。优化思想是如果回退后的字符和当前字符相同那么这次回退必然还会失配可以继续回退。vectorint getNextVal(string p) { vectorint next getNext(p); vectorint nextVal(p.size(), 0); nextVal[0] 0; for (int i 1; i p.size(); i) { if (p[i] p[next[i]]) { nextVal[i] nextVal[next[i]]; } else { nextVal[i] next[i]; } } return nextVal; }在实际做题中使用标准next数组通常就足够了nextVal优化在模式串重复字符很多时能减少一些不必要的比较但并非必须。5.2 扩展KMP的边界条件与初始化问题Z[0] 的定义在Z-Algorithm中Z[0]通常没有定义或者被定义为整个字符串的长度n因为我们不会将一个字符串与自己后缀的LCP定义为整个字符串。在实现中我们通常从i1开始计算。在解决扩展KMP问题时要特别注意题目对Z[0]的要求避免使用未定义的值。问题分隔符的选择在构造P ‘#’ S时分隔符‘#’必须确保不在P和S的字符集中出现。如果字符集是全体小写字母用‘#’是安全的。如果字符集包含所有可打印字符则需要选择一个如‘$’或‘\0’如果字符串允许等特殊字符。5.3 Manacher算法的实现陷阱陷阱1回文半径p[i]的包含关系p[i]是包含中心点的半径长度。例如对于新串“#a#b#a#”中心b在索引3p[3]4字符串“#a#b#a#”长度7半径4。这意味着回文串是t[3-41 ... 34-1]即t[0...6]。在计算原串起始位置时公式start (centerIdx - maxLen) / 2正是基于此定义推导的。陷阱2整数溢出在计算i_mirror 2 * C - i时虽然通常不会溢出但在一些极端输入或特定语言中需要注意。R和i p[i]也可能超过字符串长度但在循环条件中已被控制。性能调优建议避免频繁的字符串拼接Manacher的预处理步骤如果使用string的操作在循环中可能低效。对于性能要求极高的场景可以预先分配好2*n1的空间然后直接填充字符。使用数组代替vector在确定最大长度后可以使用原生数组int p[2*MAX_N5]来代替vector以减少动态内存分配的开销这在竞赛中有时能带来微小的性能提升。中心扩散的循环展开编译器通常能很好地优化简单的while循环手动展开收益不大。重点应放在算法逻辑的正确性上。5.4 综合问题排查清单当你的KMP/扩展KMP/Manacher代码出现错误时可以按以下清单排查问题现象可能原因检查点KMP匹配结果漏掉或错误1.next数组计算错误。2. 匹配完成后j回退逻辑错误。1. 用简单例子如“abab”手动计算next数组与程序输出对比。2. 检查找到完全匹配后是j 0还是j next[j-1]。后者才能找到重叠匹配。扩展KMP结果全为01. 分隔符选择不当导致匹配越界。2.l,r初始化或更新错误。1. 确保分隔符不在原串中出现。2. 单步调试观察i,l,r,z[i]的变化是否符合算法描述。Manacher结果比实际小1.p[i]的初始赋值min(R-i, p[i_mirror])逻辑错误。2. 中心扩散的循环边界条件错误。1. 确认i_mirror计算正确且i R时才使用快速赋值。2. 检查while循环条件是否为left 0 right n t[left]t[right]。程序运行超时1. 在KMP的while循环或Manacher的扩散循环中陷入死循环。2. 对极大输入使用了低效的字符串操作。1. 确保while循环中有使条件改变的语句如j next[j-1]或p[i]。2. 检查字符串拼接、vector初始化等操作是否在循环内频繁调用。掌握这三个算法意味着你在字符串处理领域拥有了强大的线性时间工具。理解其思想比死记模板更重要。多找一些经典题目练习从暴力解法开始再逐步优化到使用这些高级算法能让你对“优化”二字有更深刻的体会。在“kuangbin带你飞”的专题训练中建议按照由浅入深的顺序刷题先熟练掌握模板再挑战综合性的应用题最终达到灵活运用、融会贯通的境界。