算法训练营进入到 Day9 的字符串 Part02这天的重点就一个KMP 算法。说实话KMP 几乎是所有准备算法面试的人绕不开的阴影。我第一次看 KMP 的代码三分钟就晕next 数组里那个 j 跳来跳去像鬼打墙一样。后来我不背代码了老老实实把“前缀表”这个东西彻底搞清楚再回头写代码一切都顺了。这篇东西就用大白话把 KMP 拆开为什么暴力匹配慢前缀表到底是什么next 数组怎么手推出来完整代码长什么样再用一道最经典的 KMP 应用题LeetCode 459收尾。最后把我自己调试 KMP 时踩过的坑和排查习惯一块儿写出来。无论你是 Day9 刚好学到这儿还是复习阶段想把这个点啃扎实都可以照着这个思路过一遍。1. 字符串 Part02 的关键不是“字符串”1.1 从反转、哈希到匹配Part02 要解决的新问题字符串这块的知识点可以粗暴分成两类。第一类是操作型题目比如字符串逆序、字符串转数字、字母大小写转换、判断回文、统计字符频率等等这些在 Part01 里已经过了它们的核心工具大多是双指针、哈希表或者就是纯粹的模拟。第二类是匹配型题目也就是“在一个长字符串里找一个短字符串的位置”这类题看起来简单——循环嵌套就能写出来——但一旦问复杂度、问优化就引出了 KMP。Day9 的 Part02 核心就是这一件事字符串匹配。它不像是反转字符串那样写几个 swap 就能收工而是需要一个完整的算法框架来支撑。面试里让你手写strStr()、indexOf()或者“判断字符串是否包含某个子串”本质上都在考这件事。1.2 字符串匹配到底用在哪儿很多人觉得字符串匹配是面试造火箭日常工作用String.indexOf()或者std::string::find()不就行了。这个想法对一半。标准库确实封装得很好但底层原理你还是要懂因为它的应用场景实在太基础了编辑器和 IDE 里的“查找”功能就是在文本里做子串匹配。日志系统里的关键词过滤、敏感词过滤本质也是子串匹配。数据库模糊查询、爬虫去重、基因序列比对全都绕不开匹配算法。这些场景里的文本长度可能是几百万甚至上亿字符模式串也常常有几千上万的长度。如果用最简单的暴力双循环最坏情况下的乘法级复杂度会直接把程序拖垮。KMP 的价值就在这里它能把复杂度从 O(n×m) 拉回 O(nm)而且不依赖随机性无论在什么输入下都能稳定发挥。2. 先看看暴力匹配为什么这么慢2.1 暴力匹配的思路和代码长什么样在讲 KMP 之前得先知道我说的“慢”到底慢在哪儿。暴力匹配的思路很朴素从主串的每一个位置出发依次和模式串的每个字符比对如果中途发现不匹配就退回来从主串的下一个位置重新开始。假设主串是haystack模式串是needle代码写出来大概是这样int strStr(string haystack, string needle) { int n haystack.size(), m needle.size(); for (int i 0; i m n; i) { int j 0; while (j m haystack[i j] needle[j]) { j; } if (j m) { return i; } } return -1; }这个代码逻辑上没毛病。主串从位置 0 开始试匹配到一半的时候发现不匹配就把窗口往后挪一位再从头开始比对。这个“从头开始”就是问题的根源所在。2.2 一个例子看清暴力匹配的浪费你想象一个场景主串是aaaaaaaaaaaaaaaaaaaaab模式串是aaab。暴力匹配会怎么跑它从主串位置 0 开始三个a都匹配上了第四个字符比对发现是a和b不匹配然后回到位置 1又匹配上前三个a第四个又不匹配……一直这样重复到接近末尾才能匹配成功。换句话说每个位置它都要白比 3 次白跑一圈。如果主串里全是a长度是 n模式串里只有最后一个字符是b那整体比较次数大概是 m×(n−m1)也就是 O(n×m) 的级别。你可能会说“这种极端数据现实中不常见”但字符串匹配恰恰最怕的就是这种局部高度重复的数据。日志文件里的连续空格、网页里的重复字符标签、DNA 序列里的重复碱基片段都是实际会发生的高重复输入。更关键的是面试官考你 KMP也不是为了让你解决一个普通例子而是要看你在最坏情况下有没有优化意识。3. 前缀表KMP 的真正核心3.1 先说清楚什么是前缀和后缀KMP 的思路听起来很反直觉既然暴力匹配慢在失配后要回到起点那我能不能“利用已经比对过的信息”让模式串不要退回到开头而是退回到一个合理的位置这时候就要引入“前缀”和“后缀”的概念。这两个词很多人听过但具体定义容易搞混前缀一个字符串去掉最后一个字符后剩下的所有以开头字符起始的连续子串。后缀一个字符串去掉第一个字符后剩下的所有以最后一个字符结尾的连续子串。注意这里说的“前缀”和“后缀”都不包含字符串本身。比如abc的前缀是a、ab后缀是c、bc整个abc既不算前缀也不算后缀。KMP 要做的就是对模式串的每个“前缀子串”求它最长相等前后缀的长度这个长度数组就叫“前缀表”也就是常说的 next 数组。3.2 手推一个前缀表就全懂了光说定义比较抽象直接上手推。模式串取aabaaf一个字符一个字符看子串a前缀为空后缀也为空最长相等前后缀长度为 0。子串aa前缀有a后缀有a相等最长长度为 1。子串aab前缀a、aa后缀b、ab没有相等的长度为 0。子串aaba前缀a、aa、aab后缀a、ba、aba相等的最长是a长度为 1。子串aabaa前缀和后缀里都能找到aa长度为 2。子串aabaaf前缀是a、aa、aab、aaba、aabaa后缀是f、af、aaf、baaf、abaaf没有相等项长度为 0。所以aabaaf的前缀表就是[0, 1, 0, 1, 2, 0]。这个数组才是 KMP 的灵魂它记住的是模式串每一个位置如果发生失配前面已经匹配好的部分有多大一段前缀是“可以拿来直接用”的。4. 手写 KMPnext 数组与主串匹配的完整代码4.1 构建 next 数组代码与逐行解释手推前缀表没问题但要写成代码就不能每次都从头去数必须用递推。核心思路是两个指针一个 i 指向当前正在计算的位置一个 j 指向“当前已匹配的前缀长度”一边走一边更新。void getNext(vectorint next, const string s) { int j 0; next[0] 0; for (int i 1; i s.size(); i) { while (j 0 s[i] ! s[j]) { j next[j - 1]; } if (s[i] s[j]) { j; } next[i] j; } }逐行拆开看。j 0表示刚开始没有任何匹配的前缀next[0] 0是因为单字符子串的前后缀都是空的长度必然为 0。循环从i 1开始因为下标 0 已经处理过了。每轮循环要计算的是“以 s[i] 结尾的子串它的最长相等前后缀长度”。while (j 0 s[i] ! s[j])是整段代码最绕的一行。它的意思是如果新加进来的字符 s[i] 和当前要匹配的字符 s[j] 对不上j 就要回退到next[j - 1]。之所以可以回退而不是归零是因为前面已经匹配成功的那段s[0..j-1]里本身也有一段前缀和后缀相等那一段可以继续拿来用。这和主串匹配时模式串往后退是一个道理只是发生在模式串自己身上。if (s[i] s[j]) j很好理解匹配上了前缀长度加一。next[i] j把结果写进数组。注意这里求的是“最长相等前后缀长度”也就是说 next 数组的下标和模式串下标一一对应。后面匹配主串时失配的位置如果是j回退的位置就是next[j - 1]。4.2 匹配主串KMP 的主循环next 数组构建好之后匹配主串的代码几乎长一个样int strStr(string haystack, string needle) { if (needle.size() 0) return 0; vectorint next(needle.size()); getNext(next, needle); int j 0; for (int i 0; i haystack.size(); i) { while (j 0 haystack[i] ! needle[j]) { j next[j - 1]; } if (haystack[i] needle[j]) { j; } if (j needle.size()) { return i - needle.size() 1; } } return -1; }这段代码和构建 next 数组的结构非常像区别只是构建 next 时是在模式串自己和自己比匹配主串时是主串和模式串比。失配时的处理逻辑完全一致while (j 0 haystack[i] ! needle[j]) j next[j - 1];。这个 j 的回退就是暴力匹配“回到模式串开头”和 KMP“回到复用位置”的分水岭。主串的 i 从来不会回退所以主串只被扫描了一遍。当j等于模式串长度时说明匹配完成返回起点下标i - needle.size() 1。4.3 用“aabaabaaf”完整跑一遍代码看完不如亲手跑一遍。主串取aabaabaaf模式串取aabaafnext 数组是[0, 1, 0, 1, 2, 0]。初始化 i0、j0i0主串a等于模式串aj 变 1。i1主串a等于模式串aj 变 2。i2主串b等于模式串bj 变 3。i3主串a等于模式串aj 变 4。i4主串a等于模式串aj 变 5。i5主串b模式串f不匹配。此时 j5查 next[4]2j 回退到 2。主串的第 5 个字符b和模式串第 2 个字符b再比匹配j 变 3。i6主串a等于模式串aj 变 4。i7主串a等于模式串aj 变 5。i8主串f等于模式串fj 变 6。此时 j 等于模式串长度 6返回8 - 6 1 3匹配成功位置是下标 3。注意 i5 这个关键节点暴力匹配在 i5 失配时会回到主串位置 1 重新开始但 KMP 知道前面已经匹配的aabaa里前缀aa和后缀aa是相同的所以直接把模式串挪到能让这两个aa对齐的位置也就是 j 从 5 回退到 2。整个过程主串指针没有回头。5. KMP 的第一个高频变式重复子字符串5.1 解法一移动匹配的直觉做法KMP 学完不能只看匹配题目它的思想还能套到别的问题上。LeetCode 459 就是一个非常好的例子给定一个非空字符串判断它能不能由它的一个子串重复多次构成。比如abab可以由ab重复两次构成abcabcabc可以由abc重复三次构成aba不行。这道题有一个不需要 KMP 也能想到的点子如果字符串 s 由子串 p 重复 k 次构成那把 s 拼成 ss掐头去尾之后中间仍然会包含一个完整的 s。代码很干净bool repeatedSubstringPattern(string s) { string t s s; t.erase(t.begin()); t.pop_back(); return t.find(s) ! string::npos; }这个做法在大部分情况下够用实际提交也能过。但它调用了标准库的 find严格来算时间复杂度仍然要看内部实现而且它没有用到“自己重复自己”的数学本质面试追问深入一点容易答不上来。5.2 解法二KMP 与最小循环节用 KMP 可以更本质地解决这个问题。还是先求出整个字符串 s 的前缀表然后看最后一位的 next 值也就是next[n - 1]。关键结论最小循环节的长度等于 n - next[n - 1]如果 n 能被这个长度整除那么 s 就是由这个最小循环节重复构成的。bool repeatedSubstringPattern(string s) { int n s.size(); vectorint next(n); getNext(next, s); int len next[n - 1]; // 整个字符串的最长相等前后缀长度 if (len 0 n % (n - len) 0) { return true; } return false; }为什么可以这样判断拿ababab举例它的 next[n-1] 等于 4最小循环节长度为 6−42也就是ab6 能被 2 整除说明整个字符串就是ab重复三次拼出来的。反过来看abcabnext 数组最后一位是 25−235 不能被 3 整除所以不是重复子串拼接。道理也说得通最长相等前后缀为ab但这只是局部信息剩下的部分和对不齐。这个结论用前缀表的定义就能推导如果整个 s 由子串 p 重复 k 次构成那么 s 的最长相等前后缀必然长(k−1)×|p|也就是整个 s 减去一个 p 的长度。于是 n−next[n−1] 自然就是 p 的长度。前提是 next[n−1] 大于 0 且整除关系成立。我建议两道题的代码都背熟因为它们在面试里经常前后脚出现。一道负责考你能不能手写匹配逻辑一道考你能不能把 KMP 的原理迁移到“找循环节”这种抽象场景。6. 实战中踩过的坑和排查方法6.1 写 KMP 最容易出现的几个错误手写 KMP 的翻车率极高我刷题群里几乎每个人第一次写都错过。下面这张表是我整理的常见错误速查症状可能原因解决思路数组越界匹配函数里没判 needle 为空j 可能变成负数进入主循环前先判空匹配结果差 1next 数组语义不一致回退写成 j next[j]统一用原版前缀表失配回退 j next[j - 1]死循环while 里没有 j 0 的条件等于 0 时还在回退保证while (j 0 ...)才能跳出结果完全不对getNext 里 j 没有初始化或者 s[i] 和 s[j] 写成反了先手推一遍模式串的前缀表打印出来对一下只过简单样例没考虑单字符模式串、主串为空、模式串为整个主串等边界建一个自测用例清单逐个跑我自己当年最蠢的一次是把 while 里的s[i] ! s[j]误写成s[i] ! s[i - j]跑出来的 next 数组和手推完全不同浪费了整整一个钟头。6.2 调试 KMP 的独家习惯调试 KMP 有个很笨但特别有效的方法手推一个短模式串的前缀表然后用代码打印出来对比。我一般固定用aabaaf来测期望输出[0, 1, 0, 1, 2, 0]。如果这个对了说明 getNext 没问题接下来在主串匹配里出的问题只可能在主循环逻辑。自测用例我建议至少涵盖这么几种场景输入期望结果模式串为空strStr(abc, )0主串为空strStr(, a)-1单字符匹配strStr(a, a)0全相同字符strStr(aaaaa, aa)0典型 KMP 用例strStr(aabaabaaf, aabaaf)3不匹配strStr(hello, llx)-1还有一个排查技巧在 getNext 函数的循环里临时加一行输出s[i]、s[j]、j看一下每次回退到底是从哪里跳到哪里的。KMP 的失配回退有时候看起来像随机跳其实每一步都对应一个前缀后缀对齐关系把中间过程打印出来很快就不会再迷路。6.3 什么时候不该用 KMP最后说点反常识的话。KMP 虽好但不是所有字符串匹配场景都该用它。如果主串和模式串都很短比如模式串长度不超过 10暴力匹配的常数因子很小而 getNext 还要额外遍历一遍模式串、再开一个 next 数组反而更慢。实际工程里很多库函数用的是多种策略混搭短串用朴素匹配长串用 BM、Sunday 或者双向匹配。KMP 的最大价值更偏向面试、竞赛以及帮助你建立“利用已匹配信息避免重复扫描”的算法直觉。另外字符串这块的问题并不都是匹配问题。字符串排序、字符串逆序、字符串转数字、大小写转换这类题核心工具其实是排序算法、双指针和进制转换跟 KMP 是两条完全不同的线。学 Part02 的时候要清醒一点KMP 解决的是“查找子串”“找循环节”这一类问题不要一看到字符串就往这里套。我到现在还记得第一次独立写出完整 KMP 流程时那种“豁然开朗”的感觉——不是因为我背下了代码而是因为终于想清楚了 next 数组是在记录模式串自己的前后缀对应关系。建议你把aabaaf这个经典例子在手边多推几遍每推一遍对失配回退的理解就深一层。等你能在没有注释的情况下从头默写 getNext 和 strStr 并且一次跑通字符串 Part02 的核心内容就算是彻底拿下了。