算法训练营进入到 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(n+m)，而且不依赖随机性，无论在什么输入下都能稳定发挥。
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−m+1)，也就是 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. 手写 KMP：next 数组与主串匹配的完整代码
4.1 构建 next 数组：代码与逐行解释
手推前缀表没问题，但要写成代码，就不能每次都从头去数，必须用递推。核心思路是：两个指针，一个 i 指向当前正在计算的位置，一个 j 指向“当前已匹配的前缀长度”，一边走一边更新。
void getNext(vector<int>& 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; vector<int> 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"，模式串取"aabaaf"，next 数组是[0, 1, 0, 1, 2, 0]。
初始化 i=0、j=0：
- i=0：主串
a等于模式串a，j 变 1。 - i=1：主串
a等于模式串a，j 变 2。 - i=2：主串
b等于模式串b，j 变 3。 - i=3：主串
a等于模式串a，j 变 4。 - i=4：主串
a等于模式串a，j 变 5。 - i=5：主串
b，模式串f，不匹配。此时 j=5，查 next[4]=2，j 回退到 2。主串的第 5 个字符b，和模式串第 2 个字符b再比，匹配，j 变 3。 - i=6：主串
a等于模式串a，j 变 4。 - i=7：主串
a等于模式串a，j 变 5。 - i=8：主串
f等于模式串f，j 变 6。
此时 j 等于模式串长度 6，返回8 - 6 + 1 = 3，匹配成功，位置是下标 3。
注意 i=5 这个关键节点：暴力匹配在 i=5 失配时会回到主串位置 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 拼成 s+s，掐头去尾之后，中间仍然会包含一个完整的 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(); vector<int> 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−4=2，也就是"ab"，6 能被 2 整除，说明整个字符串就是"ab"重复三次拼出来的。
反过来看"abcab"，next 数组最后一位是 2，5−2=3，5 不能被 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 可能变成负数 | 进入主循环前先判空 |
| 匹配结果差 1 | next 数组语义不一致，回退写成 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 的核心内容就算是彻底拿下了。
