很多同学学 KMP 算法的时候，第一反应是背代码。背下来能过面试题，但过两天再写，又卡在next数组的边界上。我大学时候也是这样，直到后来用“书签”的视角把整个匹配过程想通了，才算真的把这套算法变成了自己的东西。这篇我就用 Java 代码为主线，把 KMP 的每一个关键决策讲清楚——为什么主串指针不用回退、next数组到底在记录什么、代码里那几个容易写错的边界是怎么来的。如果你之前看了几篇教程还是觉得隔了一层，那这篇可以帮你把那层窗户纸捅破。
1. 字符串匹配这件事，暴力解法卡在哪
1.1 一个天天遇到的匹配场景
字符串匹配听起来抽象，其实你每天都在用：在编辑器里按Ctrl+F找关键词、用indexOf判断一个字符串是否包含另一个字符串、写爬虫时从网页源码里截取某个标签段，这些全是字符串匹配。问题可以统一表述为：给定一个主串text和一个模式串pattern，找出pattern在text中第一次出现的位置，找不到就返回 -1。
最简单直观的做法是暴力匹配：从主串的每一个位置开始，挨个和模式串比较，一旦中间某个字符对不上，就把主串的起始位置往右挪一格，重新从模式串的第一个字符开始比。看一眼就懂，写起来也顺手：
public static int bruteForce(String text, String pattern) { int n = text.length(), m = pattern.length(); if (m == 0) return 0; for (int i = 0; i <= n - m; i++) { int j = 0; while (j < m && text.charAt(i + j) == pattern.charAt(j)) { j++; } if (j == m) return i; } return -1; }这段代码没有错，但在某些输入下会非常慢。假设主串是"AAAAAAAAB"，模式串是"AAAAB"，每轮都要等到最后一个字符才发现不一样，于是从主串的第 0 位试到第 4 位，每轮都比 5 次，整体接近 25 次比较。当主串长度 n 和模式串长度 m 都很大的时候，最坏情况是 O(n*m) 的复杂度。这个量级在纯文本搜索里还能忍，一旦放到基因序列比对、日志关键字扫描这种场景，直接就是灾难。
1.2 暴力匹配浪费在哪儿
暴力匹配最吃亏的地方不是“比较次数多”，而是它把已经比对过的信息全扔了。回到上面的例子：主串是从位置 0 开始的 7 个A，当我们在主串第 5 个位置发现B和模式串的最后一个字符B匹配上时，其实说明前面 4 个A都已经比较过了。如果第 5 个位置不匹配，暴力解法会从主串位置 1 重新开始算，把位置 1 到位置 4 的A再和模式串开头的A比一遍——这些明明是上一轮已经确认过的内容。
KMP 的核心思想就是：匹配失败时，主串指针不后退，只把模式串的指针往前挪到一个“还能对得上”的位置，继续比较。要做到这一点，就必须提前知道模式串自己的内部结构：它的每个前缀里，有没有一个“头和尾相同”的部分。这个信息，就是next数组。
2. next 数组是怎么算出来的：前缀函数视角
2.1 前缀表与回退位置的对应关系
先停下来做个思想实验。模式串"ABABCABAB"，如果当前已经匹配到第 7 个字符（也就是"ABABCAB"），下一个字符失配了，那你能保证已经匹配过的这一段里，最后几个字符和开头几个字符是一样的吗？答案是，可以取模式串已经匹配部分的最长公共前后缀长度，把模式串直接“平移”到这个长度上继续比。因为既然后缀和前缀相同，那这部分就不用再比较了。
所以next数组的准确含义是：next[j]表示“模式串在下标 j 处失配时，j 应该回退到的位置”。这个位置的值，本质上等于模式串[0, j-1]这个子串的最长公共前后缀长度，只是下标做了偏移。在大多数经典实现里，next[0] = -1，这个 -1 是哨兵，表示“模式串第一个字符都匹配不上，需要把主串指针也往后挪一格”，后面会细讲。
这里有一个非常容易绕晕的视角转换：最长公共前后缀是“长度”，而next里存的是“下标”。因为数组下标恰好比长度小 1（从 0 开始），所以“长度为 k 的前后缀”对应的回退位置恰好就是k，不需要额外转换。这也是为什么很多人的代码里，next[i]一会儿被解释成长度一会儿被解释成下标，越看越乱。我的建议是：就把它当成回退位置来理解和记忆，代码和逻辑能对上号。
2.2 手算一遍 next 数组
用例子说话。模式串"ABABCABAB"，逐个求next：
next[0] = -1，哨兵，没有子串可言。j = 1，子串是"A"，长度为 1 的前缀没有真后缀，最长公共前后缀长度为 0，所以next[1] = 0。j = 2，子串是"AB"，前缀A不等于后缀B，所以next[2] = 0。j = 3，子串是"ABA"，前缀A等于后缀A，最长公共前后缀长度为 1，所以next[3] = 1。j = 4，子串是"ABAB"，前缀AB等于后缀AB，长度为 2，所以next[4] = 2。j = 5，子串是"ABABC"，最长公共前后缀长度为 0，所以next[5] = 0。j = 6，子串是"ABABCA"，前缀A等于后缀A，所以next[6] = 1。j = 7，子串是"ABABCAB"，前缀AB等于后缀AB，所以next[7] = 2。j = 8，子串是"ABABCABA"，前缀ABA等于后缀ABA，所以next[8] = 3。
这种手算方法能帮你建立直观感受：next数组不是在“预测未来”，而是在统计“已经匹配成功的这段文本，末尾有多少字符和开头是重复的”。这就像你在一本书里找一句话，读到第 50 页发现读岔了，你不会回到第 1 页重来，而是翻到最近一个“看起来上下文还能接上”的位置继续。
2.3 构建 next 的 Java 实现与代码细节
手算虽好，但代码构建要更聪明一点，不能每个j都暴力求一遍前缀后缀。KMP 的构建思路是递推：假设我们已经知道next[i] = k，接下来要求next[i+1]，只需要看pattern.charAt(i)是否等于pattern.charAt(k)。如果相等，那公共前后缀长度就是k + 1；如果不相等，回退到k = next[k]，继续比较。
public static int[] buildNext(String pattern) { int m = pattern.length(); int[] next = new int[m]; if (m == 0) return next; next[0] = -1; int i = 0; // 当前已处理到的前缀末尾 int k = -1; // 当前最长公共前后缀的长度（同时作为回退位置） while (i < m - 1) { if (k == -1 || pattern.charAt(i) == pattern.charAt(k)) { i++; k++; next[i] = k; } else { k = next[k]; } } return next; }几个容易看懵的点，我逐个解释。
第一，为什么循环条件是i < m - 1？因为next[m-1]对应的子串是pattern[0..m-2]，也就是说最后一个位置本来就只需要从倒数第二个位置递推过来。代码里i初始是 0，每次匹配成功先i++再赋值，最后一次循环执行完i会变成m-1，刚好给最后一个位置赋完值，循环结束。
第二，k = next[k]这一步是在干什么？它是在“缩短公共前后缀的候选长度”。当pattern[i]不等于pattern[k]时，说明当前这个k长度的前后缀扩展不下去了，我们退而求其次，找“最长公共前后缀的前后缀”，也就是next[k]。这个过程会一直持续到k == -1，意思是连长度为 0 的前后缀都匹配不上，只能从 0 开始重新累积。
第三，pattern.charAt(i) == pattern.charAt(k)这里用的是i而不是i-1，是因为我们要求的不是“以pattern[i]结尾的最长前后缀”，而是“当前已经确认的前缀匹配长度k能不能延伸到下一个字符”。这是一个很容易写错的细节，如果你在调试时发现next数组整体偏了一位，十有八九是这里的下标没对齐。
3. 匹配阶段的 Java 实现与完整推演
3.1 KMP 匹配主流程的代码逻辑
next数组一旦构建完成，匹配阶段的代码出乎意料地短，核心就是一条规则：匹配上了就双指针同时前进，失配了就让模式串指针按next回退，主串指针原地不动。只有一种情况会让主串指针前进，那就是j == -1——模式串连第一个字符都对不上，此时只能把主串指针也往右移一位，然后重新比较。
public static int kmpSearch(String text, String pattern) { int n = text.length(), m = pattern.length(); if (m == 0) return 0; int[] next = buildNext(pattern); int i = 0; // 主串指针 int j = 0; // 模式串指针 while (i < n && j < m) { if (j == -1 || text.charAt(i) == pattern.charAt(j)) { i++; j++; } else { j = next[j]; } } return j == m ? i - j : -1; }j == -1这个分支很容易被忽略，但它很关键。想象text = "abc..."、pattern = "bcd..."，第一轮比较a和b就失配，此时j = next[0] = -1，若不加这个分支，代码会尝试访问pattern.charAt(-1)直接抛异常；加了分支后，i从 0 变成 1，j从 -1 变成 0，主串和模式串都从头开始比较。这一步本质上完成了“暴力解法里起点后移一位”的操作，区别只是主串指针只前进一次，不会再退回去扫描已经比较过的字符。
返回值为啥是i - j？因为匹配成功时i指向主串中模式串末尾的下一个位置，j等于模式串长度m，两者相减就是模式串在主串中的起始下标。如果没匹配成功，返回 -1 表示不存在。
3.2 经典例子的逐步推演
理论讲再多，不如走一遍数据。这里用算法教材最常见的例子：主串"BBC ABCDAB ABCDABCDABDE"（把空格去掉记为text），模式串"ABCDABD"。
先手算next：
| 下标 j | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| pattern[j] | A | B | C | D | A | B | D |
| next[j] | -1 | 0 | 0 | 0 | 0 | 1 | 2 |
next[5] = 1是因为子串"ABCDA"的前缀 A 等于后缀 A；next[6] = 2是因为子串"ABCDAB"的前缀 AB 等于后缀 AB。
匹配过程逐步展开：
i=0~3：B, B, C, D和A逐个比较，全部在第一个字符就失配，每次都走j = next[0] = -1分支，i变成 1、2、3、4。i=4：text[4]=A匹配pattern[0]=A，之后i=5~9连续匹配B C D A B，此时i=9,j=6，比较的字符是text[9]=C和pattern[6]=D，失配。- 失配后
j = next[6] = 2，直接跳转到pattern[2]=C，主串指针仍然在i=9。这里就体现出 KMP 的精髓：虽然我们在ABCDAB这个位置匹配了 6 个字符，但失配后我们一眼看出这段已经匹配的长度是 6，而最长公共前后缀AB长度是 2，所以AB不需要重新比较，直接从模式串下标 2 继续。 i=9,j=2：text[9]=C匹配pattern[2]=C，继续往后，i=10~12匹配D A B，到i=13,j=6，比较text[13]=C和pattern[6]=D，又失配。- 再回退
j=2，text[13]=C又刚好匹配上，继续到i=18,j=7，模式串恰好走完，返回18-7=11。检查一下text[11]到text[17]，正好是A B C D A B D。
细看第 4、5 步，你会发现主串指针从i=9推到i=13没回过一次头，每次失配都只是把模式串往右“平移”一下。这种“平移”操作的总次数是有上限的，这也是复杂度能到 O(m+n) 的根本原因。
3.3 返回结果位置的细节处理
还有一个值得说的边界：如果pattern为空字符串，匹配位置应该是 0，而不是 -1。很多语言的内置indexOf也是这么约定的，空串在任何位置都“匹配成功”，起始位置按 0 处理。我在代码开头单独用if (m == 0) return 0;挡住了这种情况，因为后续逻辑依赖next[0]，空串根本没有下标 0 可用。
另一个细节是text比pattern短的情况。匹配循环的条件i < n && j < m会自动处理这种场景：主串先遍历完，循环退出时j一定不等于m，自然返回 -1，不需要额外判断n < m。
4. KMP 里最容易踩的坑，我一次说完
4.1 next[0] 的值为什么众说纷纭
你去看网上的教程，会发现next数组的定义至少有三种：有的next[0] = -1，有的next[0] = 0，有的干脆用“前缀表”pi[i]表示长度为 i 的前缀的最长公共前后缀长度。其实这不矛盾，区别只在“你让next[j]承担什么语义”。
如果是“失配时模式串指针回退到的位置”，那next[0]必须是一个哨兵值，用来触发主串指针前进。如果定义成“最长公共前后缀长度”，那第 0 个字符没有前后缀，存 0 也合理，但匹配循环里就要额外判断j == 0时单独处理主串前进。我写代码习惯用 -1 哨兵，因为它在匹配循环里对应一个统一的分支j == -1 || equal，一劳永逸。你要是看别人的代码看到一个 +1 或 -1 的偏移，先别急着改，看看他对next的定义是什么。
4.2 回退时 k = next[k] 的终止条件
构建next数组的时候，else { k = next[k]; }这条路径是初学者最常写死循环的地方。问题在于：编译器不会提醒你，k可能一直在某个非负值上打转。我见过有人把k = next[k]写成k = next[i]或者k = k - 1，结果要么无限循环，要么回退过头跳过正确答案。
这里的终止逻辑一定要想明白：next[k]是严格小于k的，而且当k = 0时，next[0] = -1，下一轮会进入k == -1分支，把k重置并前进。只要保证每次更新k用的是next[k]，这条递归回退链必然是收敛的。如果你实在不放心，可以在 while 循环里加一个调试打印，把每轮i、k的值打出来，能看到k一路从某个正数降到 -1，心里就踏实了。
4.3 模式串为空和长度为一的特殊分支
除了pattern为空字符串要单独处理，模式串长度为 1 也是容易被忽视的边界。此时buildNext里循环条件i < m - 1也就是i < 0，循环一次都不会执行，next数组只有next[0] = -1。这种逻辑是对的：一个长度为 1 的模式串，任何失配都只能让主串指针前进，然后重新比较唯一的字符。但如果你在构建时把next[1]也赋值了，数组就越界了。
所以在写buildNext时，m == 0和m == 1的情况最好在开头都挡住，或者至少保证数组长度够用。我通常的做法是在方法入口直接处理空串，长度为 1 的情况让循环自然跳过——但前提是你能确定自己的循环边界没有越界风险。
5. 复杂度、实际应用与带改进的 next 数组
5.1 O(m+n) 是怎么摊还出来的
很多人记住了 KMP 的复杂度是 O(m+n)，但没想明白为什么。我用一个粗浅但好懂的摊还分析解释一下：匹配阶段中，i看到每个主串字符最多一次，因为i只增不减，所以主串指针移动总次数是 O(n)。模式串指针j呢？它每次失配回退都可能跳好几格，看起来不稳定，但每次回退都是因为之前至少匹配了一个字符，而“匹配一个字符”对应着i前进一次。所以j的回退次数被i的前进次数“支付”掉了，总体还是线性。构建next数组的过程同理，也可以看作一次“模式串自我匹配”，复杂度 O(m)。合起来就是 O(m+n)。
这个摊还思想比记住结论重要。面试时如果被追问“为什么不是 O(n*m)”，能把“主串指针不回退 + 回退次数受匹配次数约束”讲清楚，比背出答案要有说服力得多。
5.2 KMP 的应用场景比你想的广
实际工程里，KMP 不一定是最快的方案——对于短文本，Java 内置的indexOf用的是更轻量的优化暴力法；对于超大规模文本，Boyer-Moore、Horspool 这类从右往左匹配的算法往往更快。但 KMP 的价值在于：它的思路可以迁移到很多“看起来不像字符串匹配”的问题上。
我自己在代码里用过的一个典型场景是判断一个字符串是否由某个重复子串构成。比如"abcabcabc"应该是"abc"重复 3 次，而"abababa"不是。这类问题用前缀函数特别好解：算出模式串的最长公共前后缀长度pi[m-1]，如果m - pi[m-1]能整除m，那么这个差值就是最小循环节的长度。原理很简单：最长公共前后缀的重叠部分暗示着循环模式的存在。KMP 作为前缀函数的最常见载体，自然就成了这类问题的标准解法。
另一个实际场景是文本编辑器里的查找替换功能。如果你要对一个几 MB 的日志文件做多关键词扫描，KMP 的线性复杂度能保证不会因为某个恶意构造的输入导致界面卡死。虽然现代文本搜索用的多是更激进的算法，但 KMP 是理解这些算法的基础。
5.3 可选优化：nextval 数组
最后讲一个可选优化，叫“优化的 next 数组”，很多时候也叫nextval。核心问题是：如果回退后的位置next[j]上的字符和原来的pattern[j]是同一个字符，那么这次回退其实没有意义——我们刚在pattern[j]上失配了，回退到pattern[next[j]]如果还是同一个字符，必然还是失配，等于多跳了一次。
优化的办法是在构建next时顺手做一步“压缩”：如果pattern[i] == pattern[k]，就让next[i] = next[k]，否则才保留新算出的k。这样匹配阶段每一次回退都保证跳到“一定有机会匹配”的位置。代价是next数组不再直接对应最长公共前后缀的长度，而是一个经过剪枝的回退表。
public static int[] buildNextVal(String pattern) { int m = pattern.length(); int[] next = new int[m]; if (m == 0) return next; next[0] = -1; int i = 0, k = -1; while (i < m - 1) { if (k == -1 || pattern.charAt(i) == pattern.charAt(k)) { i++; k++; next[i] = (i < m && pattern.charAt(i) == pattern.charAt(k)) ? next[k] : k; } else { k = next[k]; } } return next; }这个优化在模式串重复字符很多时提升明显，比如前面提到的"AAAAAB"这类输入。不过要注意，优化后的next构建代码里多了一组下标判断，写错很容易越界，我建议新手先用未优化的版本跑通，需要追求极致性能再换nextval。
我自己的体会是，KMP 这个算法属于“理解前觉得难，理解后觉得顺”的典型。当初卡了我最久的不是匹配循环，而是构建next数组时k的回退逻辑——后来我把每次回退都用手工推一遍，推了七八个例子才彻底明白k = next[k]到底在收拢什么。如果你现在也被这一步卡住，别急着找更多代码看，找一个短的字符串，拿笔在纸上把每次i、k的变化都画出来，画两三个例子之后，那种“隔一层窗户纸”的感觉自然就消失了。
