1. 从字符串匹配的“笨办法”说起为什么我们需要KMP如果你写过字符串查找的代码比如在一个长文本里找一个短词最直观的想法可能就是“暴力匹配”。我刚开始刷题时也这么干让模式串的每个字符从文本串的开头一个个对齐然后逐字符比较一旦发现不匹配就把模式串往后挪一位从头再来。这个方法简单直接但效率实在不敢恭维。假设文本串长度是n模式串长度是m最坏情况下时间复杂度是O(n*m)。当处理大量数据或者模式串有一定特征时比如aaaaab在aaaaaaaaab里查找这种算法会进行大量无意义的回溯比较性能瓶颈非常明显。后来在刷LeetCode的“实现 strStr()”或者一些更复杂的文本处理题目时我逐渐接触到了KMP算法。第一次看原理时确实被那个“最长相同前后缀”和“next数组”绕得有点晕感觉是为了优化而引入的复杂概念。但真正理解并亲手实现几次后才发现它的精妙之处。KMP的核心思想是当发生不匹配时利用已经匹配成功的那部分信息避免将模式串的指针回退到开头从而跳过那些绝不可能匹配的位置。这个“已经匹配的信息”就是通过预处理模式串得到的“前缀函数”在有些实现里也叫next数组来承载的。所以今天这篇内容我想从一个刷题者的实用角度彻底拆解KMP算法。我们不只讲理论重点放在如何用Python清晰、高效地实现它并把它封装成一个可以“抄作业”的模板。无论是解决经典的字符串匹配问题还是处理一些需要用到“前后缀”思想的题目比如判断字符串是否由某个子串重复构成这个模板都能派上用场。2. 核心概念拆解前缀、后缀、前缀函数与next数组理解KMP必须先搞清楚几个关键概念。很多教程把这些概念混着用容易让人困惑。我们在这里统一一下说法并建立它们之间的联系。2.1 前缀与后缀对于一个字符串abcab前缀指从字符串开头开始的、长度从0到len(s)的所有子串。不包括字符串本身。例如,a,ab,abc,abca。后缀指以字符串结尾为结束的、长度从0到len(s)的所有子串。不包括字符串本身。例如,b,ab,cab,bcab。注意我们通常讨论的是真前缀和真后缀即不包括字符串本身。空字符串既是前缀也是后缀。2.2 前缀函数Prefix Function这是KMP算法的理论核心。对于一个长度为m的模式串p我们定义它的前缀函数π是一个长度为m的数组。π[i]的定义是子串p[0:i1]即从开头到i位置的子串中最长的、相等的真前缀和真后缀的长度。举个例子模式串p ababci0, 子串a没有真前缀和真后缀除了空串所以π[0] 0。i1, 子串ab真前缀有a真后缀有b不相等所以π[1] 0。i2, 子串aba真前缀有, a, ab真后缀有, a, ba。相等的只有a长度为1所以π[2] 1。i3, 子串abab真前缀有, a, ab, aba真后缀有, b, ab, bab。相等的有长度0和ab长度2取最长所以π[3] 2。i4, 子串ababc真前缀有, a, ab, aba, abab真后缀有, c, bc, abc, babc。没有相等的除了空串所以π[4] 0。所以模式串ababc的前缀函数π [0, 0, 1, 2, 0]。2.3 next数组next数组是前缀函数在具体实现KMP匹配时的一种实用化变形。它和前缀函数π密切相关但定义上通常有一个关键的偏移。最常见的next数组定义也是许多教材和实际代码中使用的是next[j]表示当模式串中第j个字符与文本串不匹配时模式串指针j应该回退到的位置。这个定义导致next数组通常有两种构建方式整体右移一位next[0] -1next[i] π[i-1](对于 i0)。这样next[j]直接指向了下一个比较的位置。对于ababcπ [0,0,1,2,0]则next [-1, 0, 0, 1, 2]。这是许多C/C实现中常见的形式-1作为一个特殊标志表示需要将文本串指针后移。直接使用前缀函数值有些实现尤其是Python会直接使用计算出的前缀函数数组作为next数组。在匹配时当发生不匹配如果j 0则令j π[j-1]如果j 0则移动文本串指针i。这种实现逻辑更直接地反映了前缀函数的定义。为了避免混淆在接下来的Python模板中我们将采用第二种方式即直接计算并存储前缀函数数组并称之为next数组因为它在代码中确实起到了“下一个”跳转的作用。你只需要记住在我们的模板里next[i]表示的是以i结尾的子串的最长公共前后缀长度。注意这个选择是基于Python代码的简洁性。如果你看到其他代码中的next数组开头是-1不要惊讶它们只是同一种思想的不同实现包装核心的跳转逻辑是相通的。3. 前缀函数next数组的构建算法与Python实现构建next数组即前缀函数是KMP算法的预处理阶段其本身就是一个精妙的字符串匹配过程——模式串自己匹配自己。3.1 算法思路我们使用两个指针i和j。i指向当前要计算next[i]的位置后缀的末尾。j指向前一次计算出的最长公共前后缀的长度即next[i-1]也是前缀的末尾的下一个位置。初始化next[0] 0j 0i从1开始遍历模式串。对于每个i如果p[i] p[j]说明我们可以延长当前的前后缀所以j 1然后next[i] j最后i 1继续循环。如果p[i] ! p[j]说明当前的前后缀无法延长。这时我们不能简单地将j归零因为可能存在一个更短的相同前后缀。我们利用已经计算好的next数组让j回退到next[j-1]的位置因为next[j-1]记录了p[0:j]的最长公共前后缀长度这个前缀同时也是当前后缀p[? : i]的一个可能匹配的后缀部分。然后回到步骤1继续比较。如果j已经回退到0且p[i] ! p[0]那么确实没有公共前后缀了next[i] 0i 1。这个过程就像是用模式串的前缀去匹配它的后缀j指针的回退保证了我们总是在尝试“次长”的可能匹配前后缀直到找到或确认为零。3.2 Python代码实现与逐行解析def build_next(p: str) - list: 构建模式串 p 的 next 数组 (前缀函数)。 next[i] 表示子串 p[0:i1] 的最长公共前后缀的长度。 m len(p) next_arr [0] * m # 初始化next[0] 一定是 0 j 0 # j 指向前缀的末尾位置同时代表长度 for i in range(1, m): # i 指向后缀的末尾位置 # 不匹配时j 需要不断回退直到匹配或回到开头 while j 0 and p[i] ! p[j]: j next_arr[j - 1] # 关键回退操作利用已计算的信息 # 匹配时公共前后缀长度可以增加 if p[i] p[j]: j 1 # 无论是否匹配当j0且不匹配时j依然是0设置next[i] next_arr[i] j return next_arr关键点解析while j 0 and p[i] ! p[j]: j next_arr[j - 1]这是整个构建过程的灵魂。它避免了暴力地让j一次次减1回退而是直接跳转到“上一个可能匹配的位置”。next_arr[j-1]的值代表了以p[j-1]结尾的子串的最长公共前后缀长度这个前缀部分恰好可以继续和当前后缀p[? : i]的一部分进行比较。理解这个回退是理解KMP的关键。时间复杂度虽然代码里有嵌套循环但j的增加和回退是有限制的。j最多增加m次而每次while循环j都在减少所以j减少的总次数也不会超过m。因此构建next数组的时间复杂度是O(m)。3.3 一个完整的计算示例让我们手动模拟一下p aabaaf的构建过程加深理解。i (当前后缀尾)p[i]j (更新前)p[j]操作 (while循环及if判断)j (更新后)next_arr[i]1a0ap[1]p[0]j112b1ap[2]!p[1],jnext[0]0;p[2]!p[0]003a0ap[3]p[0]j114a1ap[4]p[1]j225f2bp[5]!p[2],jnext[1]1;p[5]!p[1],jnext[0]0;p[5]!p[0]00最终得到的next_arr [0, 1, 0, 1, 2, 0]。你可以验证一下next[4]2对应子串aabaa其最长公共前后缀是aa长度为2正确。4. 利用next数组进行匹配算法与Python实现有了next数组匹配过程就变得高效了。我们不再需要回退文本串的指针i只需要在发生不匹配时回退模式串的指针j。4.1 算法思路同样使用两个指针i遍历文本串s的指针只增不减。j指向模式串p当前待匹配位置的指针。初始化i 0,j 0。遍历文本串s如果s[i] p[j]匹配成功i和j都加1。如果s[i] ! p[j]匹配失败如果j 0说明已经匹配了一部分前缀。我们让j回退到next[j-1]。注意这里i不动。回退后继续用s[i]和新的p[j]比较。如果j 0说明第一个字符就不匹配那么直接让i加1继续比较下一个文本字符。如果j等于模式串长度m说明找到了一个完整匹配。记录位置通常是i - m。然后为了继续寻找下一个可能的重叠匹配例如在aaaa里找aa我们需要让j回退j next[j-1]。4.2 Python代码实现def kmp_search(s: str, p: str) - list: 在文本串 s 中查找所有模式串 p 出现的位置。 返回一个列表包含所有匹配的起始索引。 if not p: return [] # 空模式串按题意处理通常返回[0]或[] n, m len(s), len(p) next_arr build_next(p) res [] j 0 # 模式串指针 for i in range(n): # 遍历文本串i只增不减 # 当不匹配时j回退 while j 0 and s[i] ! p[j]: j next_arr[j - 1] # 匹配时j前进 if s[i] p[j]: j 1 # 检查是否完成一次匹配 if j m: res.append(i - m 1) # 记录匹配起始位置 j next_arr[j - 1] # 回退j继续寻找可能的重叠匹配 return res4.3 匹配过程图解与复杂度分析假设s aabaabaaf,p aabaaf,next [0,1,0,1,2,0]。is[i]j (更新前)p[j]操作j (更新后)备注0a0a匹配j11a1a匹配j22b2b匹配j33a3a匹配j44a4a匹配j55b5f不匹配j0,jnext[4]22关键跳转i停在5j回退到25b2b匹配j3回退后立刻继续比较6a3a匹配j47a4a匹配j58f5f匹配j6jm匹配成功8f6-jm记录位置8-613jnext[5]00找到匹配s[3:9]可以看到在i5, j5发生不匹配时我们没有像暴力算法那样让i回到1(i5-511)j回到0重新开始。而是利用next数组让j回退到2i保持不变。这是因为s[0:5]和p[0:5]匹配的部分aabaa其最长公共前后缀是aa长度2。这意味着后缀aa已经和前缀aa对齐了我们可以直接把模式串的前缀aa滑动到与文本串的后缀aa对齐的位置即j2然后继续比较s[5]和p[2]。这跳过了中间绝不可能匹配的尝试。时间复杂度匹配过程i从0到n-1单调递增j的变化与构建next数组时类似增加和回退的总次数是线性的。因此整个KMP算法预处理匹配的时间复杂度是O(m n)空间复杂度是O(m)用于存储next数组。5. 刷题实战模板与高频应用场景理解了原理和实现我们可以把它们封装成一个即拿即用的Python刷题模板。这个模板将构建next数组和搜索函数整合在一起并处理一些边界条件。5.1 完整KMP Python模板class KMP: def __init__(self, pattern: str): self.p pattern self.m len(pattern) self.next self._build_next() def _build_next(self) - list: 构建next数组 next_arr [0] * self.m j 0 for i in range(1, self.m): while j 0 and self.p[i] ! self.p[j]: j next_arr[j - 1] if self.p[i] self.p[j]: j 1 next_arr[i] j return next_arr def search(self, text: str) - list: 在text中搜索模式串返回所有匹配的起始索引 if self.m 0: return [0] if len(text) 0 else [] # 处理空模式串的边界 n len(text) res [] j 0 for i in range(n): while j 0 and text[i] ! self.p[j]: j self.next[j - 1] if text[i] self.p[j]: j 1 if j self.m: res.append(i - self.m 1) j self.next[j - 1] # 重要继续寻找重叠匹配 return res def search_first(self, text: str) - int: 在text中搜索模式串返回第一个匹配的起始索引未找到返回-1 if self.m 0: return 0 n len(text) j 0 for i in range(n): while j 0 and text[i] ! self.p[j]: j self.next[j - 1] if text[i] self.p[j]: j 1 if j self.m: return i - self.m 1 return -1模板使用示例# 示例1查找所有匹配 kmp KMP(ababc) print(kmp.search(abababcababc)) # 输出: [2, 7] # 示例2查找第一个匹配 kmp2 KMP(abc) print(kmp2.search_first(hello abc world abc)) # 输出: 6 print(kmp2.search_first(hello world)) # 输出: -15.2 高频应用场景与LeetCode例题KMP算法及其前缀函数思想在刷题中应用广泛远不止于简单的字符串查找。场景一字符串匹配这是最直接的应用。LeetCode 28. 实现 strStr()直接套用模板的search_first方法。LeetCode 459. 重复的子字符串这道题是KMP思想的经典应用。判断一个字符串是否可以由它的一个子串重复多次构成。关键思路计算字符串s的next数组。如果s可以由子串重复构成那么s的长度n一定是其最长公共前后缀长度next[-1]的整数倍并且n % (n - next[-1]) 0。这是因为重复字符串去掉一个循环节后剩下的部分后缀必然等于前缀。例如abcabc的next[-1] 36 % (6-3) 0成立。场景二基于前缀函数的字符串性质判断前缀函数本身描述了字符串的自相似性。求字符串的最短循环节如上所述len(s) - next[-1]可能就是最短循环节的长度如果满足整除条件。求每个前缀的最长bordernext数组本身就有这个含义。border是指一个字符串既是自身前缀又是后缀的子串。场景三结合动态规划或其他算法在一些更复杂的字符串问题中next数组可以作为状态转移的一部分。LeetCode 1392. 最长快乐前缀题目就是求字符串的最长公共前后缀即next[-1]对应的那个子串。直接返回s[:next[-1]]即可。一些涉及字符串周期性的计数或DP问题可以利用next数组快速判断前缀的周期性进行状态转移。5.3 模板的变体与注意事项next[0] -1风格的实现如果你更习惯这种可以修改_build_next。初始化next[0] -1,i0, j-1循环条件为i m-1。核心回退逻辑变为j next[j]。匹配时代码也需要相应调整。两种方式效率一样选一种理解透彻即可。重叠匹配的查找注意模板中search方法在找到一次匹配后执行了j self.next[j - 1]。这保证了在类似saaaa,paa的情况下能正确找到所有重叠的匹配位置[0, 1, 2]。如果不希望重叠找到后可以直接j 0。空间优化next数组是必须的无法省去O(m)的空间。这是KMP为效率付出的空间代价。Unicode字符串Python 3中字符串是Unicode上述模板完全适用。但如果模式串非常长且字符集很大可以考虑使用字节串(bytes)或数组来获得可能的性能提升不过对于刷题环境字符串实现完全足够。6. 调试技巧与常见“坑点”即使理解了算法自己实现时也可能遇到一些bug。这里分享几个我调试KMP代码时的经验和常见问题。6.1 死循环或索引越界这通常发生在while循环的回退条件上。检查while条件while j 0 and ...中的j 0至关重要。它保证了当j回退到0时不会再去取next[-1]导致索引错误。在构建和匹配的循环中都要注意。检查next数组的访问next_arr[j - 1]只有在j 0时才是安全的。在匹配成功后回退j时也要确保j m 0所以next_arr[j - 1]安全。6.2 匹配结果遗漏或错误匹配成功后忘记回退j如果你需要找到所有匹配包括重叠的在if j m:之后必须执行j next[j-1]。如果只找第一个可以break。文本串指针i的错误移动在匹配失败且j 0时i才应该加1在我们的for循环中i是自动增加的所以我们在j0且不匹配时什么也不做让循环i即可。绝对不要在j0回退时移动i这是KMP区别于暴力算法的关键。空字符串处理模板中已经处理了模式串为空的情况。根据题目要求空串可能是任何字符串的子串通常在起始位置。文本串为空的情况也需要考虑。6.3 验证next数组的正确性对于复杂的模式串手动计算next数组容易出错。可以用以下方法验证小数据测试用几个短字符串手动计算如a,aa,ab,aba,abcab。利用定义验证写一个简单的暴力函数对于每个位置i计算子串p[:i1]的最长公共前后缀长度与你的build_next结果对比。使用已知库对比虽然Python标准库没有直接暴露KMP但你可以用str.find()或正则表达式验证匹配结果是否正确间接验证算法。6.4 性能考量虽然KMP是O(nm)但常数因子比简单的暴力算法大。对于极短的模式串比如长度小于5在随机文本中暴力算法可能更快因为它的内层循环简单。但在以下情况KMP优势明显模式串较长且含有较多重复前缀如aaaaab。需要在同一文本串中反复搜索不同的模式串可以预处理多个模式串的next数组。问题本身就需要用到前缀函数如判断重复子串。在刷题时如果题目明确提示字符串可能很长或者你发现暴力解法超时KMP通常是正确的优化方向。7. 举一反三前缀函数思想的延伸应用KMP的精髓——前缀函数next数组其“利用已匹配信息避免回溯”的思想可以迁移到其他问题。7.1 在流数据中匹配如果文本串是一个数据流无法一次性获取全部KMP依然可以工作。我们只需要维护模式串指针j和next数组。每接收到一个新的文本字符就按照匹配逻辑更新j。当j m时就发现了一个匹配。这对于实时监控日志或网络数据流中的关键字非常有用。7.2 多模式串匹配AC自动机的基础AC自动机可以看作是KMP在多模式串情况下的扩展。它用Trie树组织所有模式串并为每个节点构建一个fail指针这个fail指针的构建思想与KMP的next数组如出一辙——都是指向当前匹配失败时应该回退到的“最长可匹配后缀”对应的状态。理解KMP是理解AC自动机的重要一步。7.3 回文相关问题的启发Manacher算法用于寻找最长回文子串其核心思想也是“利用已知信息避免重复计算”与KMP有异曲同工之妙。它们都通过维护一个“最右边界”和对应的“中心”来推导新位置的信息将复杂度降为线性。掌握KMP不仅仅是掌握了一个字符串匹配算法更是掌握了一种重要的算法设计思想通过预处理构建“状态转移”信息从而在主流程中避免冗余计算。这种思想在动态规划、状态机等很多领域都有体现。下次当你遇到需要处理字符串前后缀关系、或者需要优化暴力匹配的场景时不妨想一想是否可以用前缀函数的思想来优雅地解决。