作者书到用时方恨少阅读难度零基础友好 | 全程大白话、无晦涩公式堆砌适用人群算法入门者、面试备考、学生刷题、想要吃透字符串匹配算法的小伙伴发布时间2026年5月11日 前言提到字符串匹配很多人的第一反应就是暴力枚举。但在大数据量场景下暴力算法的低效问题会被无限放大甚至直接超时。而KMP算法是字符串匹配领域的经典高效算法也是算法面试、竞赛中的高频考点。很多初学者觉得KMP难懂核心是被「前缀函数」「next数组」这些名词劝退。今天这篇博客我抛弃晦涩理论全程举例图解思维逐行代码解析带你从零吃透KMP算法搞懂它到底优化了什么、为什么快、怎么用一、什么是KMP算法1.1 算法由来KMP 是三位计算机科学家Knuth、Morris、Pratt名字的首字母缩写三人联合提出了这一线性时间字符串匹配算法完美解决了传统暴力匹配算法的冗余重复匹配问题。1.2 官方定义通俗版KMP算法是一种高效的模式串匹配算法用于在一个长文本串主串中快速查找短模板串模式串出现的位置。核心最大特点匹配失败时主串指针不回退仅利用模式串自身的重复特征跳过无效匹配步骤极大减少重复计算提升匹配效率。1.3 核心优势一句话总结暴力算法匹配错了全盘重来重复对比大量相同字符浪费时间。KMP算法记住之前的匹配结果不做无用功利用最长公共前后缀实现精准跳转。二、先搞懂暴力字符串匹配算法铺垫必看想要理解KMP的强大必须先知道暴力匹配到底差在哪里这是吃透KMP的关键前提。2.1 暴力匹配原理假设主串S长度为 n 的长字符串待查找的文本模式串T长度为 m 的短字符串要查找的目标暴力匹配逻辑非常简单粗暴主串从第0位开始和模式串逐字符对比一旦出现字符不匹配主串指针回退到下一位模式串指针归零重新从头开始匹配直到遍历完主串。2.2 暴力匹配致命缺陷我们举个直观例子主串 S AAAAAAB模式串 T AAAB匹配过程前3个A全部匹配成功第4位 A vs B 匹配失败。按照暴力算法逻辑主串指针回退、模式串归零已经匹配成功的3个A下一轮还要重新再比一遍大量重复、无效的字符对比数据量越大效率越低时间复杂度极高。三、KMP算法核心思想KMP的所有优化都只为解决一个问题避免重复匹配已经匹配过的字符。3.1 核心核心最长公共前后缀这是KMP算法的灵魂所有跳转逻辑都基于此。前缀字符串从开头开始不包含最后一个字符的所有子串后缀字符串从结尾结束不包含第一个字符的所有子串最长公共前后缀前缀和后缀中长度最长、内容完全相同的子串举个超级易懂的例子模式串子串ABABC我们看已匹配部分ABAB所有前缀A、AB、ABA、ABAB所有后缀B、AB、BAB、ABAB公共部分AB、ABAB最长公共前后缀长度 23.2 什么是Next数组部分匹配表Next数组是KMP的预处理核心数组也是新手最容易卡壳的点。Next数组定义next[i] 表示「模式串前 i 个字符组成的子串」的最长公共前后缀长度。简单说Next数组提前存好了模式串每一位的最优跳转位置。当匹配失败时不需要从头匹配直接根据Next数组跳转到对应位置完美跳过无效匹配3.3 KMP完整执行逻辑预处理阶段遍历模式串计算出完整的Next数组只需要预处理一次匹配阶段主串指针不回退模式串根据Next数组自动跳转匹配成功则双指针后移匹配失败则模式串回退到最优位置继续匹配。四、暴力匹配 VS KMP算法 详细对比我用表格通俗总结帮你彻底分清两者的差异看懂KMP的碾压式优势。对比维度暴力字符串匹配KMP算法指针回退规则主串、模式串指针均回退全盘重来主串指针永不回退仅模式串精准跳转重复计算大量重复匹配已成功的字符冗余度极高利用前缀后缀信息完全规避无效匹配预处理操作无任何预处理直接匹配预处理模式串生成Next数组一次预处理全程复用时间复杂度最坏 O(n*m)稳定 O(nm)空间复杂度O(1) 常数空间O(m) 存储Next数组适用场景短字符串、小数据量长文本匹配、多次匹配、大数据量场景核心总结KMP 用少量的空间开销换来了指数级的效率提升是典型的空间换时间的经典算法思想五、Python 完整实现KMP算法超详细注释接下来手把手实现KMP分为构建Next数组和KMP匹配主逻辑两部分代码极简、注释超细零基础也能看懂。5.1 第一步构建Next数组核心逻辑双指针遍历模式串动态更新最长公共前后缀长度。5.2 第二步KMP匹配主逻辑主串指针不回溯模式串根据Next数组动态跳转。完整可运行代码def get_next(pattern): 构建KMP的Next数组部分匹配表 :param pattern: 模式串需要查找的短字符串 :return: next数组 m len(pattern) # 初始化next数组长度和模式串一致初始值全为0 next_arr [0] * m # j前缀末尾指针i后缀末尾指针i从1开始i0无前后缀对比意义 j 0 for i in range(1, m): # 匹配失败j回退到前一位的next值循环回退直到匹配或j0 while j 0 and pattern[i] ! pattern[j]: j next_arr[j - 1] # 匹配成功前缀指针后移 if pattern[i] pattern[j]: j 1 next_arr[i] j else: # j0且不匹配最长公共前后缀为0 next_arr[i] 0 return next_arr def kmp_search(text, pattern): KMP算法匹配主函数 :param text: 主串长文本 :param pattern: 模式串目标子串 :return: 所有匹配成功的起始下标 n len(text) m len(pattern) res [] if m 0: return res # 预处理获取next数组 next_arr get_next(pattern) # j模式串指针 j 0 # 遍历主串主串指针i永不回退 for i in range(n): # 匹配失败模式串指针根据next数组回退 while j 0 and text[i] ! pattern[j]: j next_arr[j - 1] # 当前字符匹配成功双指针后移 if text[i] pattern[j]: j 1 # 模式串全部匹配完成记录结果 if j m: res.append(i - m 1) # 继续向后匹配寻找后续可能的匹配结果 j next_arr[j - 1] return res # ------------------- 测试代码 ------------------- if __name__ __main__: # 测试案例 main_text ABABCABAAABABC sub_text ABABC next_array get_next(sub_text) print(f模式串【{sub_text}】的Next数组{next_array}) result kmp_search(main_text, sub_text) if result: print(f匹配成功模式串在主串中的起始位置{result}) else: print(未匹配到目标子串)5.3 代码运行结果模式串【ABABC】的Next数组[0, 0, 1, 2, 0] 匹配成功模式串在主串中的起始位置[0, 9]六、KMP算法复杂度深度分析面试必背很多同学只会用算法不会分析复杂度面试极易扣分这里讲透原理。6.1 时间复杂度KMP算法分为两个阶段预处理阶段 匹配阶段预处理构建Next数组仅遍历一次模式串时间复杂度O(m)m为模式串长度字符串匹配阶段主串指针只增不减全程遍历一次主串时间复杂度O(n)n为主串长度总时间复杂度O(n m)属于线性时间复杂度效率极高。对比暴力算法最坏 O(n*m)数据量越大KMP优势越明显。6.2 空间复杂度算法额外开辟了一个长度为 m 的Next数组用于存储模式串的跳转信息。空间复杂度O(m)属于典型的空间换时间用极小的内存开销换取碾压级的运行效率。七、常见疑问解答新手高频坑点Q1为什么KMP主串指针不需要回退因为Next数组已经提前记录了模式串的重复结构匹配失败时我们可以通过模式串跳转复用前面已经匹配成功的部分不需要主串回头重新对比。Q2Next数组到底有什么用Next数组是KMP的导航地图告诉模式串匹配失败时不用归零直接跳到哪个位置继续匹配最合适彻底避免无效计算。Q3什么时候用KMP什么时候用暴力匹配短字符串、单次匹配、数据量极小暴力匹配足够用代码更简单长文本、多次匹配、大数据量、刷题/面试场景优先KMP。八、全文总结本篇博客从零拆解了KMP算法的全部核心知识点我们简单复盘一下本质优化暴力匹配消除重复无效的字符对比核心最长公共前后缀 Next数组预处理特性主串指针不回退模式串精准跳转复杂度时间O(nm)空间O(m)价值字符串匹配最优解之一面试、竞赛、工程高频应用。KMP算法看似抽象本质就是记住过往匹配结果不做无用功理解了最长公共前后缀就掌握了KMP 90%的核心作者寄语算法学习切勿死记硬背理解底层逻辑才能举一反三、灵活运用。持续深耕基础方能从容应对各种复杂场景✨