KMP这个算法，大概是很多人在代码随想录刷题路上遇到的第一道硬骨头。别看前面的链表、哈希表、双指针都能顺风顺水写过去，一到第九天的KMP，很多人直接卡了一周。我自己带过不少人刷题，几乎每个人都会在next数组这一步懵掉：视频看了一遍觉得懂了，关上屏幕自己写，不是死循环就是越界，要不就是匹配结果不对。最折磨人的是，网上一搜KMP，各种版本的next数组定义还不一样，有的从0开始存，有的整体右移，有的第一位是-1，代码长得完全不一样，越看越乱。
今天这篇就想把KMP这件事彻底讲明白。我不会只丢给你一段代码让你背，而是把next数组为什么这么算、匹配的时候为什么要这么跳、不同版本的代码差异到底在哪，全部掰开揉碎讲清楚。不管你是准备面试、应付考试，还是单纯想把字符串匹配搞明白，这篇都适用。读完你至少能做到：手推任意模式串的next数组，手写匹配代码不卡壳，并且能跟面试官把“为什么复杂度是O(n+m)”这件事说清楚。
1. KMP到底在解决什么问题
1.1 先看朴素的字符串匹配有多亏
假设我们要在主串 s = "aabaabaaf" 里找模式串 p = "aabaaf"，最简单粗暴的方式就是从左往右一位一位试：先用主串的第0位开始和模式串对齐，逐位比较；如果中间某一位失配了，就把整个模式串往右移一格，再从模式串第0位开始重新比较。
这个过程用人话说就是：主串的指针 i 一会儿往前走一会儿往回退，模式串指针 j 动不动就归零。最坏情况下，主串长度为 n，模式串长度为 m，每移动一次主串指针就要比较 m 次，总复杂度是 O(n×m)。当模式串很长、且重复字符很多的时候，这个乘法关系会非常吓人。我见过很多人在暴力匹配。“aabaaf”这种例子里还能忍，如果模式串是"aaaaab"，主串是"aaaaaaaaab"，暴力匹配几乎每个位置都要完整比到最后一个字符才失配，那个效率是真的没法看。
1.2 KMP的核心思想：让主串指针少回头
KMP算法的核心突破点在于：主串的指针 i 不回头，一直往前走；失配时只让模式串的指针 j 往回跳到一个合适的位置。“合适”这两个字是关键，它意味着我们要提前预处理模式串，记住一些信息，让下次比较能够直接从某个位置开始，而不是每次都要回到模式串的第0位重来。
这个预处理结果就是next数组。你可以把next数组理解成模式串自己给自己画的“回退地图”：当第 j 位失配时，不用从头开始，而是跳到地图上指定的位置继续比。为什么能这样？因为主串中已经比较过的那些字符里，有一部分其实已经和模式串的某个前缀匹配上了，这部分信息完全可以复用，不需要白白浪费掉。
2. next数组的本质：最长相等前后缀
2.1 什么是前缀和后缀
在讲next数组之前，必须先搞懂两个概念。一个字符串的前缀，是包含串首字符、但不包含串尾字符的任意子串；后缀，是包含串尾字符、但不包含串首字符的任意子串。
以模式串 "aabaa" 为例。它的前缀有："a"、"aa"、"aab"、"aaba"，注意 "aabaa" 本身不算自己的前缀。它的后缀有："a"、"aa"、"baa"、"abaa"，同样 "aabaa" 本身不算。这前后两组里，长度相等又内容相同的，就是相等前后缀。比如 "a" 是，"aa" 也是；长度更长的就没有了。
为什么要关心前缀后缀？因为字符串匹配失败的瞬间，我们已经知道主串当前位置之前的若干字符完全等于模式串的某段前缀。这一段里，前缀和后缀的重叠情况，直接决定了模式串能往右滑多远。你可以把它想成两组积木：左边一摞是前缀，右边一摞是后缀，只有当它们高度一样、花色也一样的时候，才能稳稳地叠在一起复用。
2.2 最长相等前后缀怎么算
对于模式串的每一个位置 i，我们关心的是：从第0位到第 i 位这个子串中，最长相等前后缀的长度是多少。这个长度就是 next[i] 的值，也叫做这个子串的部分匹配表（Partial Match Table）数值。
拿 "aabaaf" 来举例，从第0位开始依次看：
- 子串 "a"：只有1个字符，前缀和后缀都是空集，最长相等前后缀长度为0。
- 子串 "aa"：前缀有 "a"，后缀有 "a"，最长相等前后缀长度为1。
- 子串 "aab"：前缀有 "a"、"aa"，后缀有 "b"、"ab"，没有相等的，长度为0。
- 子串 "aaba"：前缀 "a"、"aa"、"aab"，后缀 "a"、"ba"、"aba"，只有 "a" 相等，长度为1。
- 子串 "aabaa"：前缀 "a"、"aa"、"aab"、"aaba"，后缀 "a"、"aa"、"baa"、"abaa"，"a" 和 "aa" 相等，最长的是 "aa"，长度为2。
- 子串 "aabaaf"：前缀有一堆，后缀末尾是 "f"，没有相等的情况，长度为0。
所以模式串 "aabaaf" 每个位置对应的最长相等前后缀长度就是：0、1、0、1、2、0。这个数组就是我们说的next数组，写成 [0, 1, 0, 1, 2, 0]。
2.3 next数组的不同版本：新手最大的坑
这里必须专门讲一下版本问题，因为网上资料实在太乱了。同一个模式串，在不同教材里可能给出完全不同的next数组，但背后的逻辑其实是一回事，只是存法不同。
| 版本 | "aabaaf" 的 next 数组 | 失配时回退写法 | 说明 |
|---|---|---|---|
| 前缀表原样存储（代码随想录常用） | [0, 1, 0, 1, 2, 0] | j = next[j - 1] | 数组长度和模式串相同，下标0固定为0 |
| 右移一位，首位置-1 | [-1, 0, 1, 0, 1, 2] | j = next[j]（注意处理-1） | 失配位直接用当前下标查表 |
| 经典教材右移再减1 | [-1, 0, 1, 0, 1, 2, 0] | j = next[j] | next[0] 是哨兵-1，严格来说值等于前一位的前缀表值 |
看到这个表格你可能更晕了，但我建议的做法是：刷题和面试就死磕第一个版本，也就是代码随想录推荐的版本。它最直观，下标和模式串一一对应，不容易在回退的时候把下标搞错。至于其他版本，优先级很低，等你能熟练写出第一个版本之后，再去看就很容易理解它们是怎么变出来的了。
3. 手把手推一遍next数组
3.1 初始化与整体思路
next数组的构建过程，本质上是模式串自己和自己做KMP匹配。逻辑上我们用两个指针：j 表示已经匹配成功的前缀长度，i 表示当前正在处理的后缀末尾位置。
初始状态是 i = 1，j = 0，next[0] = 0 是固定的，因为单字符没有相等前后缀。然后 i 从1开始一直遍历到模式串末尾，每一步做的事情可以概括成三段：不相等就回退，相等就前进，最后记录 next[i]。
为了让你看得清楚，我写一个Python风格的伪代码：
def build_next(p): n = len(p) next = [0] * n j = 0 for i in range(1, n): while j > 0 and p[i] != p[j]: j = next[j - 1] if p[i] == p[j]: j += 1 next[i] = j return next这个代码只有十几行，但里面的 while 回退是绝大多数人理解不了的坎。我接下来就用 "aabaaf" 一步一步走给你看。
3.2 以 "aabaaf" 为例的逐步推演
我用一个表格把每次循环的现场记录整理出来：
| i | p[i] | 当前j | 比较情况 | 执行动作 | 最终j | next[i] |
|---|---|---|---|---|---|---|
| 0 | a | 0 | 初始化 | 固定next[0]=0 | 0 | 0 |
| 1 | a | 0 | p[1]==p[0] | j加1 | 1 | 1 |
| 2 | b | 1 | p[2]!=p[1] | 回退j=next[0]=0，p[2]仍不等于p[0]，j保持0 | 0 | 0 |
| 3 | a | 0 | p[3]==p[0] | j加1 | 1 | 1 |
| 4 | a | 1 | p[4]==p[1] | j加1 | 2 | 2 |
| 5 | f | 2 | p[5]!=p[2] | 回退j=next[1]=1，p[5]!=p[1]；再回退j=next[0]=0，p[5]!=p[0] | 0 | 0 |
这个推演过程建议你拿笔在纸上自己画一遍，尤其是 i=5 那一步，是从 j=2 一路回退到 j=0，中间经历了两次回退。很多人的困惑就在这：为什么 p[5] 和 p[2] 不相等之后，要去看 next[1]，而不是直接把 j 清零？因为 next[1]=1，它表示的是子串 "aa" 的最长相等前后缀长度是1。也就是说，虽然当前尝试扩展的前缀后缀接不上了，但更短的前后缀可能还有希望，所以要先跳到那个短一截的位置再试试，而不是彻底放弃。
3.3 回退代码里的j=next[j-1]到底在干什么
这里必须把 next[j-1] 的意思讲透。当 p[i] != p[j] 时，说明以 i 结尾的后缀没法直接接上长度为 j 的前缀。但我们并不想直接清零，因为 p[0..j-1] 这一段已经匹配成功了，这段内部可能还有重叠的前后缀。
next[j-1] 表示的是子串 p[0..j-1] 的最长相等前后缀长度。我们把这个长度作为新的 j，就相当于把“已经匹配好的部分”缩到最短的重复段，然后再拿 p[i] 去和新的 p[j] 比较。如果还是不相等，就继续用同样的逻辑回退，直到 j 变成0，或者遇到相等的字符为止。
这里常见的误区是把回退写成 j = next[i] 或者 j = next[j]，版本不同写法确实不同，但在当前这个前缀表原样存储的版本里，回退对象必须是 next[j-1]，不是 next[j]，也不是 next[i]。我见过好多人改代码把这里写错，结果就是要么数组越界，要么结果永远差一位。
为了验证你确实懂了，建议再手推一个连续回退的例子，比如模式串 "aabaaa" 的next数组。它的推演过程中，i=5 时 p[5]='a' 先和 p[2]='b' 比，不相等，回退到 j=1，p[5]='a' 和 p[1]='a' 相等，这时候 j=2，next[5]=2。这个例子的价值在于：它展示了回退之后可能立刻就有新的字符能匹配上，而不是回退到底才重新匹配。很多教程只讲 "aabaaf"，会让你误以为回退都是回退到0，其实不是。
4. 真正跑一遍KMP匹配
4.1 匹配主流程代码
next数组构建好了，匹配就变得非常简单。主串指针 i 从头走到尾，模式串指针 j 负责跟着走，失配时根据next数组回退。完整代码如下：
def kmp_search(s, p): next = build_next(p) j = 0 for i in range(len(s)): while j > 0 and s[i] != p[j]: j = next[j - 1] if s[i] == p[j]: j += 1 if j == len(p): return i - j + 1 # 找到了，返回起始下标 return -1 # 没找到这段代码和构建next的代码结构惊人地相似，因为KMP本身就是“一个算法用两遍”：构建next是模式串匹配自己，查找是主串匹配模式串。理解了这个对称性，你在面试时就很容易少写很多代码。
4.2 用例子验证匹配过程
继续用主串 s = "aabaabaaf"、模式串 p = "aabaaf" 跑一遍。上面的推演已经得到 next = [0, 1, 0, 1, 2, 0]，匹配过程的现场如下：
| 主串下标i | 主串字符 | 当前模式串下标j | 比较结果 | 动作 |
|---|---|---|---|---|
| 0 | a | 0 | 相等 | j=1 |
| 1 | a | 1 | 相等 | j=2 |
| 2 | b | 2 | 相等 | j=3 |
| 3 | a | 3 | 相等 | j=4 |
| 4 | a | 4 | 相等 | j=5 |
| 5 | b | 5 | 失配 | j=next[4]=2，回退后重新比较 |
| 5 | b | 2 | b==b，相等 | j=3 |
| 6 | a | 3 | 相等 | j=4 |
| 7 | a | 4 | 相等 | j=5 |
| 8 | f | 5 | 相等 | j=6，j==len(p)，匹配成功 |
匹配成功的位置 i=8，返回的起始下标是 i - j + 1 = 8 - 6 + 1 = 3，也就是主串从下标3开始是 "aabaaf"。你可以自己数一下，s[3..8] 恰好就是 "aabaaf"，完全正确。
这里有个很直观的对比：同样这个例子，暴力匹配需要比较15次字符，而KMP只比较了10次，省下的次数全部来自失配后的“有脑回退”，而不是“无脑从头再来”。
4.3 为什么时间复杂度是O(n+m)
很多人背结论说KMP是O(n+m)，但不知道这个结论为什么成立。道理其实不复杂：主串指针 i 在整个匹配过程中单调递增，最多走 n 步；模式串指针 j 每次增大都发生在匹配成功时，最多增大 m 次。而 while 循环里的回退操作每次都会让 j 至少减少1，但 j 的总增大量不超过 m，所以回退总次数也不会超过 m。整体加起来，主串遍历 n 次，模式串相关操作 m 次左右，总复杂度就是 O(n+m)。
也就是说，KMP把原本的乘法复杂度变成了加法复杂度，这是质的提升。字符串匹配在大文本检索、编辑器查找、日志分析里是个高频操作，数据量一大，这个提升就非常明显了。
5. 我踩过的坑和常见问题汇总
5.1 next数组构建中的死循环与越界
我见过最多的错误，是初学者把 while 循环的条件写成了 while p[i] != p[j]，漏掉了 j > 0 这个前置条件。这样当 j 已经回退到0但 p[i] 仍然不等于 p[0] 时，代码会继续执行 j = next[j - 1]，也就是 j = next[-1]，直接数组越界，程序崩溃。这个 j > 0 相当于一道路障，拦住你回退到负数的情况。
另外还有个细节：如果 p[i] != p[0]，此时 while 不会进入，if 判断也不成立，j 保持0，next[i] 赋值为0。也就是说，next[i] 等于0表示以 i 结尾的这个子串没有任何相等前后缀。这个逻辑很多第一次写的人在 if 之后忘了赋值，导致 next 数组后面全是默认值，匹配结果自然不对。
5.2 不同next数组版本的混淆问题
这是KMP最大的坑。你背了一个版本的写法，结果在网上搜代码发现别人的写法长这样：
void getNext(string p, int next[]) { int j = 0, k = -1; next[0] = -1; while (j < p.length() - 1) { if (k == -1 || p[j] == p[k]) { ++j; ++k; next[j] = k; } else { k = next[k]; } } }不要说新手，有几年经验的工程师看到这代码也得愣一下。这是经典教材里把k初始化为-1的写法，和代码随想录的写法完全两套。我的建议很明确：认准一种版本，写熟它，面试时就按那个版本写。如果面试官问“能说下另一种版本吗”，你只需要说“我知道next数组有右移和减1的变体，核心逻辑是一样的，只是存储方式不同”，然后对比一下就行，不用真去默写第三种。
5.3 匹配成功后如何找下一个匹配位置
如果面试题要求找出所有匹配位置，而不是第一个，匹配成功之后不能直接 return。正确的做法是：在 j == len(p) 时记录当前起始下标，然后执行 j = next[j - 1]，继续往后走。这一步的原理是：匹配成功的一段里，仍然可能存在重叠的前后缀，所以通过回退可以无缝衔接下一次匹配，主串指针完全不需要回退。
举个例子，模式串 "aa"，主串 "aaaa"，最暴力的匹配能找到3个位置：下标0、1、2。用KMP找全部位置时，第一次匹配成功 j=2，记录下标0，然后 j=next[1]=1，继续遍历，在主串下标2时再次匹配成功，记录下标1，如此往复。这个技巧在很多字符串题目里直接能用，比如统计一段文本里某个单词出现的次数。
5.4 面试高频追问：nextval是什么
如果面试官想加深难度，大概率会问：“next数组还有没有优化的空间？”这里引入nextval的概念。nextval的核心优化点是：如果回退后的那个字符和失配时的字符一样，那这次回退其实没有意义，因为下一次比较肯定还是会失配。比如模式串 "aaaaab" 的 next 数组是 [0,1,2,3,4,0]，在某个 a 失配时，回退到更早的一个 a，比较时还是会失配，白白浪费一次比较。nextval只是把这种情况的next值继续往前传递，跳过这些无效比较。理解这个优化的关键还是在于先把基础next数组写熟，否则容易把自己的思路绕进去。
5.5 一个实用性建议：先背场景再背代码
最后说一个我自己的经验。KMP这个算法，除非你天天写字符串匹配，否则搁置三个月很容易忘。我建议你不要只背代码，而是记住两个关键场景：一个是主串指针 i 永不回头，一个是失配时查 next[j-1]。只要这两个画面在脑子里立住了，代码是可以现场推出来的。我自己后来每次写KMP，都是从“自己匹配自己”这个场景开始，现场构建next，反而比死记硬背更不容易出错。
另外，刷题时如果只是想通过代码随想录第九天的内容，不用过分追求一次写对。我建议先在纸上把 next 数组手推三遍，再用代码验证，然后再跑匹配流程。这个过程看似慢，其实比反复看视频高效得多。KMP值得你花这一两个小时，因为字符串匹配的思想在后续很多题目里都会用到，比如重复子串判断、回文串预处理，都藏着KMP的影子。
