字符串匹配是开发里绕不开的活文本编辑器里的查找替换、日志系统里筛报错关键字、爬虫清洗HTML里的标签、甚至数据库里的LIKE查询底层都离不开它。而要聊字符串匹配KMP算法绝对是绕不开的一座山。我见过不少人面试前背了一堆next数组的模板真到写的时候却调不对边界一失配就懵。这篇不是教科书式的推导我会把KMP拆开揉碎从暴力匹配为什么慢讲起到next数组到底在干嘛最后给出可以直接抄的Python代码和调试经验让你看完能真正写出来而不是仅仅背下来。KMP全称是Knuth-Morris-Pratt算法由三位计算机科学家联合提出核心思想概括成一句话就是**当模式串与主串失配时充分利用已经匹配过的信息让模式串向右滑动尽可能远同时主串指针绝不回头。**它解决的是在O(nm)时间内完成文本匹配的问题适合对匹配性能有要求、或者需要在长文本里反复查询的场景。无论你是准备面试、做文本处理工具还是想搞懂后续的AC自动机、正则引擎这篇都值得认真读完。1. 先搞懂痛点暴力匹配到底慢在哪里1.1 朴素匹配的运行逻辑在讲KMP之前我们得先做一个看起来有点傻的事把最朴素的暴力匹配从头到尾走一遍搞清楚它到底慢在哪。假设主串text是ABXABCABCABX模式串pattern是ABCABX我们要在主串里找pattern第一次出现的位置。暴力匹配的做法是主串从位置0开始模式串也从0开始逐个字符比较一旦中途失配主串回到这次比较的起始位置的下一个位置模式串回到0再从头开始比。走一遍就是主串0~2位A B X和模式串前两位A B匹配第3位X和C失配。主串指针回到1模式串归零。主串1位B和模式串0位A比不匹配主串2位X和模式串0位A比不匹配……直到主串5位开始A B C A B依次对上然后主串第10位X和模式串第5位X对上了命中。这个流程看起来也没多慢对吧但如果text长度是100万pattern长度是1万最坏情况下每比较到pattern的尾部才失配主串就要回退几千上万次再从头开始比时间复杂度就退化到了O(n*m)。1.2 重复比较的根源是信息丢弃暴力匹配最大的浪费在哪看这个场景主串是ABABABCABABABCABABABC模式串是ABABABC。当我们在主串位置0匹配到ABABA后第5位是B模式串第5位也是B第6位主串是C模式串是C按理说能匹配上但如果前面某一步失配了比如匹配到主串位置2、模式串位置2时发现不一样暴力算法会怎么做主串回到位置1模式串回到0。可我们明明已经知道主串0~1是AB、模式串0~1是AB这些信息在回退后就全部作废了下一次又要从B和A开始重新比。换句话说暴力匹配在失配时把之前比对过的字符全忘了然后重新做一遍无用功。那些已经看过的字符在模式串滑回去之后大概率还是会匹配上其中的一部分这部分完全可以跳过去。1.3 KMP的破题思路把已知信息存起来KMP的想法非常朴素既然暴力匹配的主要浪费在于反复回头从头开始那我就把模式串自身的信息预处理好存成一张表。每次失配时查一下表看看模式串可以安全地滑动多远不需要回溯主串。这张表就是next数组也叫前缀函数表。它记录的是模式串每个前缀子串的最长相等前后缀长度。理解这句话之前你要先知道什么叫前缀和后缀。前缀就是从开头开始的连续子串后缀就是从结尾结束的连续子串。比如对ABCAB来说真前缀A、AB、ABC、ABCA真后缀B、AB、CAB、BCAB相等的且长度最长的前后缀就是AB长度为2所以ABCAB的最长相等前后缀长度就是2。这也就是为什么失配时模式串不用从0重新开始而可以直接从第2位开始继续比——因为主串里已经读过的后缀AB正好等于模式串的前缀AB这部分是确定的匹配没必要再比一遍。这就是KMP的全部灵魂。剩下的问题只有一个怎么高效地求出每个前缀的最长相等前后缀长度。2. KMP核心前缀函数到底在算什么2.1 先手算一遍next数组光看定义容易晕我们手算一组。以模式串ABCABX为例逐个计算每个前缀的next值。前缀最长相等前后缀next值A无长度为1不能取真前后缀0ABA和B不相等0ABCAB和BC、A和C都不等0ABCA前缀A等于后缀A1ABCAB前缀AB等于后缀AB2ABCABX没有相等的0你发现问题没有ABCA的next是1ABCAB的next是2刚好是在上一个前缀的基础上如果当前新加的字符能和上次匹配的前缀的下一位对上next值就加1。这就有了一种递推的思路。再举一个体现回退的例子模式串ABABACA0AB0ABA1A等于AABAB2AB等于ABABABA3ABA等于ABAABABAC0注意倒数第二个前缀ABABA的next是3但最后一个ABABAC一下子变成了0这说明新加的一个C直接把前面所有匹配延续全部打断了。递推的时候如果一直顺着加1到这里就会出错必须想办法回退。这就是构建next数组里最需要小心的逻辑。2.2 为什么失配时看的是next[j-1]很多人写KMP时会纠结一个细节失配时到底用next[j]还是next[j-1]这取决于next数组的下标定义。我的建议是统一采用next[i]表示模式串前i1个字符即下标0到i这个前缀的最长相等前后缀长度。在这种定义下如果当前匹配到了模式串下标j处失配说明pattern[0..j-1]这段已经全部匹配成功。我们希望模式串滑动后能保留这段已匹配字符串最长的、同时也是模式串开头的那部分也就是查找pattern[0..j-1]这个前缀的最长相等前后缀长度。而这个值恰好存放在next[j-1]里。所以失配回退的代码就是while j 0 and text[i] ! pattern[j]: j next[j - 1]用一个小例子验证主串ABXABCABCABX模式串ABCABX。匹配到主串位置2时主串是X模式串是C此时已匹配的部分是AB查next[1]等于0所以j回到0相当于模式串完全从头再来。再看另一个例子假设已匹配ABCAB后失配查next[4]等于2于是j从5回到2下一次直接比较模式串[2]也就是C和当前主串字符因为模式串前两个字符AB和主串已匹配部分的后两个字符AB是确定相等的不会再重复比较。2.3 理解最长相等前后缀时的常见误读网上很多资料会把next数组说成部分匹配表但如果你直接在代码里套很容易产生一个误解以为next[j]就是失配后j要回退去的位置。在不少教科书版本里确实是这么定义的他们把整个数组整体右移一位next[0]设为-1。这导致很多人在切换版本时一脸懵。我不推荐记那种-1版本理由有两点一是下标语义不直观容易和人解释不清二是写边界判断时-1的处理非常容易出错。我们统一用后缀数组版本也就是next[i]直接存最长相等前后缀长度。这样构建和匹配的逻辑完全对称调试起来也清晰。3. 手写实现从前缀表到完整KMP3.1 构建next数组的代码逐行解读下面这段Python代码就是next数组的构建逻辑和KMP匹配本身惊人地相似都是双指针失配回退def build_next(pattern: str) - list[int]: m len(pattern) nxt [0] * m j 0 # j表示当前前缀长度也就是最长相等前后缀的长度 for i in range(1, m): # 失配时向前回退回退到上一个可能匹配的前缀 while j 0 and pattern[i] ! pattern[j]: j nxt[j - 1] # 能匹配则前缀长度加1 if pattern[i] pattern[j]: j 1 nxt[i] j return nxt这段代码里最核心的是while循环。以模式串ABABAC为例i1字符B和pattern[0]即A不相等j保持0nxt[1]0i2A和A相等j加1变成1nxt[2]1i3B和B相等j加1变成2nxt[3]2i4A和A相等j加1变成3nxt[4]3i5C和pattern[3]即B比较不相等。此时j3需要回退jnxt[2]1。回退后再比较C和pattern[1]即B还是不相等继续回退jnxt[0]0。退出循环C和pattern[0]即A也不相等j保持0。nxt[5]0整个过程的关键就是**回退不是直接回到0而是回到上一个最长相等前后缀的位置一层层向上尝试。**这个逐层回退保证了不会漏掉更短但匹配的前缀同时均摊下来每个字符最多回退一次构建next数组的总复杂度是O(m)。3.2 匹配主流程代码有了next数组匹配流程就非常简单了def kmp_search(text: str, pattern: str) - int: if pattern : return 0 n, m len(text), len(pattern) nxt build_next(pattern) j 0 for i in range(n): # 失配时模式串指针回退主串指针i不回退 while j 0 and text[i] ! pattern[j]: j nxt[j - 1] if text[i] pattern[j]: j 1 if j m: return i - m 1 return -1这里有个很重要的细节我踩过坑当文本指针i遍历时只要text[i]和pattern[j]相等j就增加一旦j等于m说明整个模式串匹配完毕直接返回起始位置i - m 1。如果主串里根本没有模式串最后返回-1。如果你需要找所有匹配位置而不是只找第一个那么在命中后不能直接return而是记录当前位置然后执行j nxt[j-1]让模式串像失配一样回退继续往后扫。比如要在AAAAA里找所有AA第一次命中在位置0回退后j变成1下次匹配还能从位置1继续命中。3.3 复杂度分析均摊才是O(nm)KMP的复杂度是O(nm)但很多人不理解为什么while循环回退不会把复杂度拖成O(n*m)。这里的关键是均摊分析匹配过程中主串指针i严格递增每次比较要么j加1要么j通过while回退。j每次回退都会变小而j增加的次数不超过m所以总回退次数也不可能超过m因为回退总和不可能大于之前增长的总和。更精确地说构建next时每个i会触发若干次回退但所有回退累计次数是O(m)级别而i本身就只有m次因此总操作次数是O(mm)。匹配阶段同理主串最多遍历n次回退次数累计不超过匹配过程中j增长的总次数也是O(m)级别所以总复杂度O(nm)。对比一下暴力匹配的最坏情况O(n*m)在文本很长、模式串也很长的场景下这个差距是巨大的。比如100万字符的文本里找一个5万字符的模式串暴力最坏要跑5000亿次比较KMP只需要150万次左右。4. 实战测试与调试实录4.1 几个必测的边界用例算法写完了千万别急着收工。我每次写完KMP都会跑下面这一组测试基本能覆盖掉所有常见边界问题测试场景textpattern期望结果空模式串anything0空主串abc-1模式串比主串长abcabcd-1完全重复字符AAAAAAAA0连续重叠匹配ABABABAABA0失配后回退复用ABXABCABCABXABCABX6完全一致KMPKMPKMP0完全不一致ABCDEFXYZ-1特别提醒模式串比主串长这个用例很多实现没考虑mn的情况KMP照样会遍历完整个text然后返回-1这没问题但你要确保它不会越界访问pattern。我们匹配循环里有j m的隐含约束吗没有但如果text遍历完了j还没到m自然就是-1。而j达到m时会及时返回所以不会越界。再提一个经典坑如果pattern只有一个字符比如A匹配BA期望返回1。代码里nxt长度为1nxt[0]0j的while循环根本进不去匹配时j1后立即返回没有问题。4.2 常见的实现错误和排查方法实际写KMP的过程中我踩过而且看别人踩过最多的坑集中在三个地方**第一个坑回退时忘记判断j0。**如果失配时j已经是0你还去执行jnxt[-1]直接越界。就算你用的是传统-1版本也可能把j变成-1导致后续逻辑混乱。所以while里必须写j 0 and ...顺序不能反。**第二个坑构建next时误把pattern[i]和pattern[i-1]比较。**这个非常隐蔽。你在构建next时j代表的是已经匹配的前缀长度所以pattern[j]是下一个要进行匹配的字符。如果你改成pattern[i-1]那求出来的根本不是最长相等前后缀而是当前字符和前一个字符是否相等结果自然全错。**第三个坑失配回退后没有继续比较当前字符。**很多人写匹配时遇到失配就直接jnxt[j-1]然后continue认为下一轮循环再比较就行。但这样会导致主串当前字符被跳过漏掉匹配。正确做法是回退之后继续在同一轮循环里比较text[i]和新的pattern[j]因为当前字符还没被消费。排查技巧在构建next和匹配的while循环里临时加打印比如print(i, j, text[i], pattern[j])一眼就能看出回退路径是否符合预期。用手算的next数组做对照是最有效的调试手段。4.3 和BM、Sunday、RK算法的横向对比聊KMP绕不开还有什么其他字符串匹配算法。实际工程里不一定总是用KMP因为不同算法有自己的舒适区。我把几个主流的放在一起对比算法预处理复杂度匹配复杂度最坏空间复杂度核心特点朴素BFO(1)O(n*m)O(1)简单无脑适合短文本KMPO(m)O(nm)O(m)主串指针不回退稳定性强BMO(m)O(n*m)但平均非常快O(m)从后往前匹配坏字符规则SundayO(m)O(n*m)实际极快O(m)看失配后下一个字符决定跳跃Rabin-KarpO(m)O(n*m)平均O(nm)O(1)哈希滚动适合多模式匹配KMP的优势是最坏情况下的线性保证这在日志扫描、输入法拼音串匹配这类对稳定性有要求的场景里很重要。BM和Sunday在平均情况下往往更快尤其BM在英文文本里效率很高因为它们利用了跳过更多字符的策略。但工程上的很多库比如某些正则引擎用的是多种策略结合的思路而不是只押注一种算法。如果你要在一个很长的文本里查一个很短的模式串Sunday往往是最快的代码也简单但如果你要处理的是二进制流、DNA序列这类字符集很小、重复度极高的内容KMP的线性保证就比Sunday那种大概率跳过的策略稳得多。4.4 真实排查案例一次少匹配一次的教训有一次我在处理一批日志文件想从里面提取所有包含ERROR:DB_Timeout的行。用KMP写了一个查找所有匹配的版本结果在某一行的日志里明明出现了两次关键字程序只返回了第一次的位置。查到最后发现原因命中后我直接return没有处理找到后继续搜索的逻辑。正确的做法是命中后先记录位置然后执行j nxt[j-1]让模式串回退到次长相等前后缀的位置继续向后匹配。举个具体例子textDB_Timeout_DB_TimeoutpatternDB_Timeout第一次命中后如果不回退j主串指针继续往后走j已经等于m后面会越界。如果回退jnxt[m-1]因为模式的next是0j回到0主串指针继续走第二次命中就能正常找到了。这是KMP做查找全部时最容易忽略的细节面试如果追问怎么找所有出现位置其实就是在考察这个点。5. 个人经验与扩展思考写到这里我还是想多说几句自己的体会。KMP这个算法第一遍学的时候特别容易卡在next数组上因为它的构建过程本身就是个mini版的KMP匹配只不过匹配的双方都是模式串自己。我当时是用手算程序输出对照的办法把ABABAC这类串的next数组手推了十几遍推到能把每一步j的变化背下来写代码就不容易出错了。给准备面试或者想深入学的朋友一个建议不要死记模板而是把next[i]当成模式串前i1个字符的最长公共前后缀长度来理解然后自己推导一遍构建过程。一旦理解了这个数组的语义失配回退、命中后回退这些操作就全都能推导出来了。还有一点经验KMP的思想不只是用在字符串匹配上。next数组求出来的其实就是字符串的循环节信息所以KMP可以用来找字符串是否存在循环节、最小循环周期是多少。比如ABABAB的next值是4用len - next[-1]就能算出最小循环节长度为2这个结论在处理周期性文本时非常有用。再往后学AC自动机你会发现它本质上是把KMP的前缀函数扩展到了多模式匹配的字典树Trie上理解了KMP再去看AC自动机就顺理成章了。我在实际项目中一开始以为KMP只能在竞赛里用后来做日志清洗、敏感词过滤、基因序列比对时都真切地感受到了它的价值。尤其是敏感词过滤需要对大量短模式串做匹配KMP配合AC自动机构建词库匹配器连几万条词都能在毫秒级跑完。如果你的项目里也频繁处理字符串匹配我强烈建议不要满足于能跑就行花一个下午把KMP吃透后面的红利会持续很久。