学习目标理解字符串匹配问题的定义和应用场景掌握暴力匹配算法的原理及其局限性深入理解KMP算法的核心思想最长公共前后缀能够手写next数组的构建代码熟练掌握KMP算法的代码实现理解KMP算法的复杂度分析一、引言字符串匹配的重要性1.1 什么是字符串匹配字符串匹配是计算机科学中最基础也是最重要的算法问题之一。简单来说就是在给定的文本Text中查找模式Pattern出现的位置。问题定义输入文本串T和模式串P输出模式串P在文本串T中第一次匹配成功的位置索引如果不存在则返回 -1这个问题在实际开发中有广泛的应用场景文本编辑器中的搜索功能当我们使用 CtrlF 在文档中搜索关键词时底层就是字符串匹配算法在发挥作用。高效的匹配算法能让搜索在毫秒级别完成即使面对百万字的长文档。生物信息学中的DNA序列比对在基因组学研究中科学家需要在大规模DNA序列数据库中查找特定的基因片段。字符串匹配算法是BLAST等序列比对工具的核心组件。网络入侵检测系统IDS通过匹配网络数据包中的特征字符串来检测恶意流量如检测HTTP请求中的攻击payload。编译器中的词法分析编译器在识别关键字、标识符时需要判断当前字符序列是否匹配预定义的模式。1.2 暴力匹配简单但低效在探讨KMP算法之前我们先了解暴力匹配Brute Force方法因为理解其局限性才能更好理解KMP的价值。暴力匹配的思想从文本串的第一个字符开始依次与模式串的每个字符比较。如果当前字符匹配成功则继续比较下一个字符如果匹配失败则将模式串整体向右移动一位从文本串的下一个位置重新开始匹配。暴力匹配代码实现defbrute_force(text:str,pattern:str)-int: 暴力匹配算法 时间复杂度: O(n * m)其中 n len(text), m len(pattern) 空间复杂度: O(1) n,mlen(text),len(pattern)# 模式串长度不能超过文本串ifmn:return-1foriinrange(n-m1):j0whilejmandtext[ij]pattern[j]:j1ifjm:returni# 匹配成功返回起始位置return-1# 匹配失败暴力匹配的问题考虑最坏情况文本串T AAAAAAAAB模式串P AAAB。在这种情况下每次匹配都要比较到模式串的最后一个字符才发现不匹配导致大量重复比较。当模式串较长时效率极低。时间复杂度分析最好情况O(n)模式串第一个字符就不匹配最坏情况O(n × m)如上述最坏情况平均情况O(n × m)二、KMP算法的诞生2.1 三位科学家的贡献KMP算法由三位计算机科学家于1977年共同发表他们分别是Donald Knuth计算机科学泰斗《计算机程序设计艺术》作者Vaughan Pratt算法设计专家James Morris编译器专家这三位科学家在同一家餐厅用餐时讨论出了这个算法因此在论文发表时采用了他们姓氏的首字母组合——KMP。2.2 核心思想避免不必要的回溯暴力匹配算法的低效之处在于当匹配失败时文本串的指针会回退而模式串的指针总是回到起点。这种指针回退导致大量重复比较。KMP算法的核心洞察当匹配失败时我们不需要回退文本串的指针而是利用已经部分匹配的信息将模式串滑动到合适的位置继续匹配。关键问题滑动多少如何确定这个滑动距离答案利用模式串自身的结构特性——最长公共前后缀。三、最长公共前后缀理解KMP的钥匙3.1 前缀与后缀的定义在深入理解KMP之前必须明确前缀和后缀的概念前缀Prefix包含首字符但不包含尾字符的所有子串。例如对于字符串 “ABCD”前缀A, AB, ABC非前缀ABCD这是整个字符串后缀Suffix包含尾字符但不包含首字符的所有子串。例如对于字符串 “ABCD”后缀D, CD, BCD非前缀ABCD公共前后缀同时是前缀和后缀的子串。例如对于字符串 “ABAB”前缀A, AB, ABA后缀B, AB, BAB公共前后缀A, AB其中最长的是AB长度为23.2 最长公共前后缀表对于模式串的每个位置我们计算以该位置结尾的子串的最长公共前后缀长度。这个信息存储在一个数组中通常称为next数组或prefix数组。对于模式串 “ABABC” 的 next 数组计算位置 i子串前缀后缀最长公共前后缀next[i]0A--空-11ABAB空02ABAA, ABA, BAA13ABABA, AB, ABAB, AB, BABAB24ABABCA, AB, ABA, ABABC, BC, ABC, BABC空03.3 next数组的代码实现方法一暴力计算defbuild_next_brutal(pattern:str)-list: 暴力方法构建 next 数组 时间复杂度: O(m²) mlen(pattern)nxt[0]*mforiinrange(1,m):# 计算 pattern[0:i1] 的最长公共前后缀max_len0forjinrange(1,i1):ifpattern[:j]pattern[i-j1:i1]:max_lenj nxt[i]max_lenreturnnxt方法二动态规划优化推荐defbuild_next(pattern:str)-list: KMP 算法构建 next 数组 时间复杂度: O(m) 空间复杂度: O(m) mlen(pattern)nxt[-1][0]*(m-1)# 初始化next[0] -1 是哨兵# i: 正在计算的位置也是当前最长公共前后缀的起始位置# j: 当前已知的最长公共前后缀长度i,j1,0whileim-1:ifj-1orpattern[i]pattern[j]:# 匹配成功继续扩展i1j1nxt[i]jelse:# 匹配失败回溯jnxt[j]returnnxt动态规划思想的图解模式串: A B A B C 索引: 0 1 2 3 4 next: -1 0 0 1 2 计算过程: - i1, j0: pattern[1]B ! pattern[0]A, jnext[0]-1 j-1, i, j next[2]0 (为什么是2而不是1?) 等等让我重新分析: next[0] -1 i1, j0: pattern[1]B ! pattern[0]A, jnext[0]-1 j-1: i2, j0, next[2]0 i2, j0: pattern[2]A pattern[0]A i3, j1, next[3]1 i3, j1: pattern[3]B pattern[1]B i4, j2, next[4]2 最终: next [-1, 0, 0, 1, 2]四、KMP算法完整实现4.1 算法框架KMP算法的核心思想可以用一句话概括当文本串和模式串在位置 i 和 j 匹配失败时利用 next[j] 的信息将模式串滑动到合适的位置继续匹配避免了文本串指针的回退。4.2 完整代码实现defkmp_search(text:str,pattern:str)-int: KMP 字符串匹配算法 参数: text: 文本串 pattern: 模式串 返回: 模式串在文本串中首次匹配的起始索引不存在则返回 -1 时间复杂度: O(n m) 空间复杂度: O(m) n,mlen(text),len(pattern)ifm0:return0ifnm:return-1# 1. 构建 next 数组nxtbuild_next(pattern)# 2. 匹配过程i,j0,0# i: 文本串指针, j: 模式串指针whileinandjm:ifj-1ortext[i]pattern[j]:# 匹配成功或 j 回退到起点i1j1else:# 匹配失败根据 next 数组回退模式串指针jnxt[j]ifjm:returni-j# 匹配成功return-1# 匹配失败4.3 算法执行过程图解示例文本串T ABABABCABA模式串P ABABCnext数组: [-1, 0, 0, 1, 2] 匹配过程: T: A B A B A B C A B A P: A B A B C ↑ j2 匹配到 T[3]B 和 P[3]Bj4 T: A B A B A B C A B A P: A B A B C ↑ j4 T[4]A, P[4]C匹配失败 根据 next[4]2将 j 回退到 2 T: A B A B A B C A B A P: A B A B C ↑ j2 继续匹配... 最终匹配成功返回位置 2五、next数组的优化5.1 nextval数组标准的next数组在某些情况下还存在优化空间。考虑以下情况问题场景模式串P AAAABnext [-1, 0, 1, 2, 3]当文本串T AAAB模式串P AAAAB匹配时T: A A A B P: A A A A B ↑ 不匹配 根据 next[3]2 回退 P: A A A A B ↑ 不匹配 继续回退...直到 j-1可以看到当 pattern[j] pattern[next[j]] 时回退后的字符仍然是相同的必然导致再次匹配失败。优化方案构建nextval数组当 pattern[j] pattern[next[j]] 时直接跳过。defbuild_nextval(pattern:str)-list: 优化后的 next 数组 (nextval) mlen(pattern)nxt[-1][0]*(m-1)i,j1,0whileim-1:ifj-1orpattern[i]pattern[j]:i1j1# 优化如果 pattern[i] pattern[j]则 nxt[i] nxt[j]ifpattern[i]pattern[j]:nxt[i]nxt[j]else:nxt[i]jelse:jnxt[j]returnnxt六、LeetCode真题实战6.1 题目28. 找出字符串中第一个匹配项的下标题目描述给你两个字符串haystack和needle请你在haystack字符串中找出needle字符串出现的第一个位置下标从 0 开始。如果不存在则返回-1。解题代码classSolution:defstrStr(self,haystack:str,needle:str)-int: 方法一KMP 算法 时间复杂度: O(n m) 空间复杂度: O(m) ifnotneedle:return0n,mlen(haystack),len(needle)ifnm:return-1# 构建 next 数组nxt[-1]*mforiinrange(1,m):jnxt[i-1]whilej0andneedle[i]!needle[j1]:jnxt[j]ifneedle[i]needle[j1]:nxt[i]j1# KMP 匹配i,j0,0whileinandjm:ifj-1orhaystack[i]needle[j]:i1j1else:jnxt[j]returni-mifjmelse-1defstrStr_better(self,haystack:str,needle:str)-int: 方法二Python 内置函数面试时的备选方案 虽然面试官可能要求手写KMP但了解内置方法也很重要 try:returnhaystack.index(needle)exceptValueError:return-16.2 相关题目推荐459. 重复的子字符串判断字符串是否能由子串重复构成28. 找出字符串中第一个匹配项的下标KMP标准应用214. 最短回文串KMP构造前缀匹配后缀七、复杂度分析7.1 时间复杂度构建 next 数组O(m)每个字符最多被访问两次扩展一次可能回退一次总比较次数 ≤ 2mKMP 匹配过程O(n)文本串指针 i 只增加不回退模式串指针 j 的回退次数受限于 i 的增加次数总比较次数 ≤ 2n总体时间复杂度O(n m)7.2 空间复杂度next 数组O(m)其他变量O(1)总体空间复杂度O(m)八、KMP的变种与扩展8.1 Z算法Z算法是KMP思想的另一个应用用于计算字符串中每个位置与主串的最长前缀匹配长度。defz_algorithm(s:str)-list: Z算法计算 Z[i] s[0:n] 与 s[i:n] 的最长公共前缀长度 时间复杂度: O(n) nlen(s)z[0]*n lr0# [l, r] 是 Z-box当前已知的最长匹配区间foriinrange(1,n):ifir:z[i]min(r-i1,z[i-l])whileiz[i]nands[z[i]]s[iz[i]]:z[i]1ifiz[i]-1r:l,ri,iz[i]-1z[0]nreturnz8.2 Sunday算法Sunday算法是另一种高效的字符串匹配算法在某些场景下比KMP更快。defsunday_search(text:str,pattern:str)-int: Sunday 算法 时间复杂度: 平均 O(n)最坏 O(n*m) n,mlen(text),len(pattern)ifmn:return-1# 构建移动表move{c:m1forcinset(text)}fori,cinenumerate(pattern):move[c]m-i i0whilein-m:matchTrueforjinrange(m):iftext[ij]!pattern[j]:matchFalsebreakifmatch:returniifimn:imove.get(text[im],m1)else:breakreturn-1九、面试要点总结9.1 必问知识点KMP的核心思想避免不必要的回溯利用已匹配信息next数组的含义next[i] 表示模式串[0,i]子串的最长公共前后缀长度next数组的构建动态规划思想理解双指针维护匹配失败时的处理j next[j]而非 j j - 19.2 手写代码要点# 标准模板务必背熟defkmp(text,pattern):# 边界检查ifnotpattern:return0n,mlen(text),len(pattern)# 1. 构建 next 数组nxt[-1]*m i,j1,0whileim-1:ifj-1orpattern[i]pattern[j]:i1j1nxt[i]jelse:jnxt[j]# 2. KMP 匹配ij0whileinandjm:ifj-1ortext[i]pattern[j]:i1j1else:jnxt[j]returni-jifjmelse-19.3 回答话术问题解释一下KMP算法的工作原理参考答案KMP算法的核心思想是利用已匹配的信息来避免暴力匹配中的回溯。当匹配失败时不是简单地将模式串右移一位而是利用预处理得到的next数组将模式串滑动到合适的位置继续匹配。具体来说next数组记录了模式串中每个位置的最长公共前后缀长度。当在位置j匹配失败时我们不需要重新从模式串的开头开始匹配而是将j回退到next[j]的位置继续匹配因为模式串[0, next[j])这部分已经与文本串匹配成功了。这种方法将时间复杂度从暴力匹配的O(n×m)降低到O(nm)。十、总结KMP算法是字符串匹配领域的经典算法其核心思想——“利用已有信息避免重复计算”——在计算机科学的许多领域都有应用。学习建议理解next数组的含义是掌握KMP的关键手动模拟几轮匹配过程加深理解能够独立写出完整的next数组构建代码理解为什么next[0]-1以及这个设计的好处延伸阅读AC自动机多模式串匹配后缀数组解决更多字符串问题Manacher算法最长回文子串推荐阅读《算法导论》第32章字符串匹配《数据结构与算法分析》KMP专题LeetCode字符串匹配题目合集