KMP算法详解：从next数组构建到Java实现与性能优化

1. 先从暴力匹配聊起为什么字符串匹配会慢做开发这些年谁没写过几段字符串查找的代码。比如要判断一个长文本里有没有某个关键词最直觉的做法是从头开始挨个比不对就往后挪一位再比。这个写法在任何一本算法书里都叫暴力匹配代码长这样public static int bruteForce(String text, String pattern) { int n text.length(); int m pattern.length(); 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; }这个思路本质是枚举所有可能的起始位置最坏情况是什么样呢举个极端例子文本是AAAAAAAAAAAAAAAAAB模式串是AAAAB。每次匹配都要比较到模式串最后一个字符才发现不对然后只能把起始位置往右挪一位。这种场景下时间复杂度是 O(n * m)n 是文本长度m 是模式串长度。一旦文本是几兆字节模式串又命中了这种“前面全对、最后一位错”的分布性能会直接崩盘。我当时第一次意识到这个问题是在处理一个日志分析需求的时候。几千万行的日志里要找出所有包含某个特定错误码的行写了个暴力匹配结果跑了几分钟没出结果。同事看了一眼说“你怎么不用 KMP”我当时的表情大概和“啊什么”差不多。后来补了课才明白KMP 就是把这种 O(n*m) 的最坏情况压到 O(nm) 的算法而且思路还挺巧妙。这篇文章就专门把 KMP 算法讲透。从它最核心的“前缀函数”思想到 next 数组的构建原理再到完整的 Java 实现和常见踩坑点一次性讲清楚。适合这些人看数据结构学过但没吃透的、面试前临时抱佛脚的、以及工作中真的遇到大文本匹配想找个靠谱方案的开发者。2. KMP 核心思想模式串要自己学会“记忆”暴力匹配之所以慢核心问题在于每次失配模式串就从头部重新开始而文本串的指针还要回退。但实际上文本串已经比较过的那部分字符我们是有“记忆”的——那些字符的信息明明在手里却被白白丢掉了。2.1 一个生活化的类比想象你在读一本纸质书要找一段话。你从第一页开始扫中间某几页看起来很像目标内容但比下去发现第 17 行对不上。暴力做法是翻回开头重新开始一段一段找但聪明人会想刚才对不上的那页前面的内容和目标已经有部分重叠了我是不是可以从中段接着往下看不用整个翻回去KMP 的原理就类似这个“书签”思维失配之后模式串不必回到开头而是利用之前匹配过程中的已知信息跳到下一个可能匹配的位置。这个“跳到哪”的动作就是由 next 数组决定的。2.2 前缀、后缀与最大相等前后缀这里需要一个严格的定义。对字符串s的某个前缀子串s[0..i]前缀是指除了最后一个字符以外从开头算起的任意长度子串比如ABABA的前缀有A、AB、ABA、ABAB。后缀是指除了第一个字符以外从结尾算起的任意长度子串比如ABABA的后缀有BABA、ABA、BA、A。最大相等前后缀就是既属于前缀又属于后缀的最长子串但不能是字符串本身。注意一个关键点我们找的是真前缀和真后缀不能把整个子串自己算进去。否则每个子串的最大相等前后缀长度都是它自己没有任何区分度了。举例ABABA前缀候选A、AB、ABA、ABAB后缀候选BABA、ABA、BA、A交集A、ABA最长的是ABA长度 3。这个 3 代表什么意思呢它代表在这个子串内部有长度 3 的前缀和长度 3 的后缀完全相同。将来一旦以这个子串结尾的匹配过程失配了模式串可以直接往后挪动让这段已经验证过的后缀同时也是前缀直接对齐省掉重新比较的过程。2.3 next 数组的定义KMP 中的 next 数组也叫前缀表、PMT 表就是为模式串的每个位置i存储上面这个“最大相等前后缀长度”。具体定义next[i] 在模式串 P 中P[0..i] 的最大相等前后缀的长度比如模式串ABABCAiP[0..i]最大相等前后缀next[i]0A无长度为001AB无A≠B02ABAA13ABABAB24ABABC无05ABABCAA1next 数组构建完成后匹配过程在P[j]处失配时j不是归零而是跳到next[j-1]或next[j]取决于数组版本——因为模式串前缀中有一截和刚才失配位置之前的已匹配段重合这截可以直接复用不必重新和文本串比一遍。3. next 数组的构建KMP 的发动机理解了概念之后问题就变成如何高效地算出模式串每个位置的 next 值。显然不能对每个i都暴力扫描一遍所有前缀后缀那样构建复杂度就是 O(m²)整体算法又退化回去了。KMP 的巧妙之处在于next 数组可以递推构建总体复杂度只有 O(m)。3.1 递推构建的思路假设模式串是P我们处理到位置i并且已经知道了前面所有位置的next值。现在要算next[i]本质上就是问在P[0..i-1]的某个最大相等前后缀的基础上P[i]能不能让这个匹配继续延伸。具体的递推逻辑这样理解设j next[i-1]也就是P[0..i-1]的最大相等前后缀长度。这时候P[0..j-1]与P[i-j..i-1]是相同的。比较P[i]和P[j]如果相等那么P[0..i]的最大相等前后缀就是j1即next[i] j 1。如果不相等就不能直接扩展了需要把j回退到next[j-1]再看看P[i]和新的P[j]是否相等。这个过程可以循环执行直到匹配成功或j退到 0。这里有个容易绕进去的地方为什么回退的是j而不是别的因为P[0..j-1]本身也有自己的最大相等前后缀这两截在失配后是可以继续对齐的。这是整个 KMP 算法最核心的“跳转传递性”理解了它KMP 就懂了一半。3.2 一种简化写法next 数组整体右移版本严格的 PMT 定义下失配时要看next[j-1]下标要减 1代码容易写乱。很多教材和面试题里用的是另一种常见变体把 next 数组整体右移一位并且next[0] -1。这种写法在匹配代码里更顺手失配时直接j next[j]不需要减 1。这种变体下next[i] 的含义变成当P[i]失配时模式串应该跳转到的位置。这种变体我实际用得最多代码写起来也更干净public static int[] buildNext(String pattern) { int m pattern.length(); int[] next new int[m]; next[0] -1; int i 0; int j -1; while (i m - 1) { if (j -1 || pattern.charAt(i) pattern.charAt(j)) { i; j; next[i] j; } else { j next[j]; } } return next; }这段代码为什么这样写一步步拆解i扫遍模式串的每个位置j记录的是“当前前缀后缀匹配的长度减一”也就是已经对齐的长度。初始j -1表示还没有任何前缀后缀对齐。当P[i] P[j]时说明相等前后缀可以延长i和j同时后移并记录next[i] j。失配时j next[j]正是之前说的回退逻辑。遇到j -1时说明无路可退那就重头开始i前进next[i] 0。注意这个版本的 next 值含义和 PMT 定义略有不同next[i] 存的是 A 失配时要跳到的模式串位置而不是最大相等前后缀长度。很多人面试时栽在这里——背了模板但没搞清楚数组下标含义边界一改就翻车。3.3 完整演示一遍构建过程手跑一遍模式串ABABCA会用这种右移版 nexti0, j-1进入j-1分支i1, j0, next[1]0i1, j0P[1]BP[0]A不相等jnext[0]-1i1, j-1进入j-1分支i2, j0, next[2]0i2, j0P[2]AP[0]A相等i3, j1, next[3]1i3, j1P[3]BP[1]B相等i4, j2, next[4]2i4, j2P[4]CP[2]A不相等jnext[2]0i4, j0P[4]CP[0]A不相等jnext[0]-1i4, j-1进入j-1分支i5, j0, next[5]0i5, j0P[5]AP[0]A相等i6, j1循环结束i m-1 为 false最终 next 数组[-1, 0, 0, 1, 2, 0]。这一步建议你自己在纸上多跑几个不同模式串比如AAAAA、ABCDABC跑熟了之后对 KMP 的“跳转”直觉会强很多。4. KMP 匹配流程与完整 Java 实现next 数组构建完毕匹配阶段就简单多了。核心思想文本串的指针i永远不回退模式串的指针j根据 next 数组跳转。4.1 匹配代码public static int kmpSearch(String text, String pattern) { int n text.length(); int 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]; } } if (j m) { return i - j; // 匹配起始位置 } return -1; }代码很短但每个判断都有讲究。j -1的情况在什么时候会出现就是模式串第一个字符就失配时。此时next[0] -1回退后j变成-1下一轮循环直接进入j -1分支i前进、j归 0相当于文本串下一个字符和模式串第一个字符重新开始比较。4.2 可视化一个匹配过程用文本ABABABCA和模式串ABABCA来演示第一阶段前面都比较顺利步骤ij文本[i]模式[j]动作100AA匹配i1, j1211BB匹配i2, j2322AA匹配i3, j3433BB匹配i4, j4544AC失配jnext[4]2关键在第 5 步文本串第 4 位是A模式串第 4 位是C失配。暴力匹配会直接把文本串指针回退到 1重新来。KMP 呢j跳到2意味着模式串的AB前缀直接对齐了文本串刚匹配过的AB后缀不用回退文本串。第二阶段利用 next 跳转后步骤ij文本[i]模式[j]动作642AA匹配i5, j3753BB匹配i6, j4864CC匹配i7, j5975AA匹配i8, j6j m成立返回i - j 8 - 6 2。也就是说匹配从文本串下标 2 开始ABABCA正好在ABABABCA的 2 到 7 位置。这个例子能清晰看到 KMP 的优势文本串指针从头到尾只走了 8 步没有一次回退。模式串虽然在中途经历了一次跳转但跳转是 O(1) 的数组访问整体依旧线性。4.3 Java 工程化完整版本做工程时经常需要的不只是“找第一次出现”而是找全部匹配位置。下面的版本做了个小扩展public class KmpMatcher { public static int[] buildNext(String pattern) { int m pattern.length(); int[] next new int[m]; next[0] -1; int i 0; int j -1; while (i m - 1) { if (j -1 || pattern.charAt(i) pattern.charAt(j)) { i; j; next[i] j; } else { j next[j]; } } return next; } public static ListInteger findAll(String text, String pattern) { ListInteger positions new ArrayList(); int n text.length(); int m pattern.length(); if (m 0) { return positions; } int[] next buildNext(pattern); int i 0; int j 0; while (i n) { if (j -1 || text.charAt(i) pattern.charAt(j)) { i; j; } else { j next[j]; } if (j m) { positions.add(i - j); j next[j - 1]; // 继续寻找下一个匹配 } } return positions; } public static void main(String[] args) { String text ABABABCAABABCAB; String pattern ABABCA; System.out.println(findAll(text, pattern)); // 输出 [2, 9] } }这里有个细节找到一个匹配后下一步怎么做很多人直接把j归零但这样会漏掉“重叠匹配”的情况。比如文本AAAAA模式AA期望结果是[0, 1, 2, 3]。所以找到匹配后要执行j next[j-1]让模式串回退到“最后一个已匹配字符的前缀后缀重合点”继续匹配。这是工程实现中特别容易踩的坑。5. 复杂度分析为什么总时间是线性的很多人背过结论KMP 时间复杂度 O(nm)空间复杂度 O(m)。但问到为什么就说不清了。5.1 构建 next 数组的时间复杂度构建过程中指针i只增不减总共移动 m-1 次。而指针j虽然会回退但每次回退都是通过j next[j]而next[j]严格小于j。这里有个关键观察j 每前进一步都是伴随 i 前进时才发生的j 每次回退都会消耗一次之前 j 前进的“里程”。所以 j 的前进次数和回退次数是绑定的整体回退次数不会超过前进次数。总归是 O(m)。5.2 匹配阶段的时间复杂度同理文本串指针i从 0 到 n 只增不减模式串指针j类似地“有借有还”。整个匹配过程最多执行 2n 次主循环每次要么 i 前进要么 j 回退回退总量不超过前进总量。所以匹配阶段是 O(n)。5.3 一个直觉类比可以把 KMP 的线性理解为两个指针在各自数组上运动总路程是有限的每个元素最多被访问常数次。相比之下暴力匹配的问题在于文本串指针经常回退同一个字符可能被反复比较很多次。KMP 牺牲 O(m) 的空间换来“空间换时间”的效果——用一张 next 表记录模式串自身的折叠信息把重复比较全部消除。注意KMP 不是唯一的线性匹配算法还有 BM 算法Boyer-Moore、Horspool、Sunday 等变体。BM 在实际文本编辑器中常表现更好因为它在失配时能跳得更远。但 KMP 的优点是理论复杂度稳定不存在最坏情况退化而且特别适合模式串较短或字符集较小的场景。6. 实践中的常见问题与变体这部分内容是实际写代码、面试和刷题中反复会遇到的高频坑。6.1 next 数组的两种风格别混用市面上 KMP 教程用的 next 数组主要有两类版本next[0]失配跳转典型实现PMT 版0j next[j-1]教科书常见右移版-1j next[j]竞赛/面试常用两种都能跑通但混用就会出 bug。比如你把 PMT 版概念的 next 值直接塞进右移版的匹配代码里边界条件全乱。我建议选一种记住理解透它的下标含义另外那种知道存在即可。6.2 模式串为空工程中文本查找模式串为空字符串时应该返回什么一般返回 0表示空串在任何位置都能匹配。很多实现没处理这个边界直接buildNext里m0时数组长度 0后面匹配代码访问next[j]直接越界。6.3 匹配完成后的重叠匹配前面提到的findAll里找到匹配后要j next[j-1]而不是归零。这个细节在 LeetCode 类的题里很常见比如“找出所有子串出现位置”。很多人第一次写就挂在重叠匹配上。6.4 优化版 next 数组原版 KMP 有个小缺陷模式串AAAA与文本串AAAAB匹配时一旦在最后一个 A 处失配j会沿着 next 链一路回退3 → 2 → 1 → 0做了 3 次无效跳转因为这几个位置的字符都是 A回退后比较必然再次失配。优化的思路是如果回退后P[j] P[i]直接改跳next[j]而不是j。也就是在构建时多判断一次if (j -1 || pattern.charAt(i) pattern.charAt(j)) { i; j; if (i m) { next[i] (pattern.charAt(i) ! pattern.charAt(j)) ? j : next[j]; } } else { j next[j]; }这种做法叫 nextval 数组能进一步消除重复的无意义比较。不过它会让构建代码难读一点考试和面试时打不打优化版看个人熟练度——平时我写业务代码会用原版刷题追求效率时用优化版。6.5 Java 里的现成轮子聊到 KMP有同学可能会问Java 的 String.indexOf 内部用 KMP 吗实话实说String.indexOf在不同 JDK 版本里实现不同OpenJDK 里老的实现是基于暴力匹配加少量优化的对短字符串暴力反而快新版本里也并没有完整采用 KMP。Java 的正则Pattern类用的是自己的一套状态机/自动机匹配算法。所以如果你的场景模式串是固定的且文本很长、要求稳定性能手写 KMP 依然有价值如果只是查找一个短词直接用indexOf就够了不必过度设计。6.6 字符集与字节流匹配KMP 本身不关心字符集。但实际项目中对中文内容的匹配如果直接把字符串转换为 UTF-8 字节数组再匹配要小心“半个汉字”的问题——因为一个汉字 3 个字节如果失配发生在多字节字符中间跳转可能撕裂字符边界。更稳妥的做法是直接基于 String 的 char 或码点做匹配不要先转字节。7. KMP 的应用场景它不只是面试题很多人觉得 KMP 只是面试造火箭工作用不上。实际上它的使用范围比想象中大得多。7.1 文本编辑器的查找功能文本编辑器里按 CtrlF 查找关键词底层就是某种字符串匹配算法。对于超大文件几百 MB 的日志暴力匹配会卡顿而线性复杂度的 KMP 或 BM 可以保证查找体验。7.2 敏感词过滤做过内容审核的同学应该不陌生。把一个敏感词列表里的词作为模式串在用户输入内容中逐个匹配。虽然这种情况有更好的多模式匹配算法比如 AC 自动机但 AC 自动机本身就是在 KMP 思想上的扩展——把单条模式串的 next 跳转扩展成多模式串的 goto/fail 跳转。所以理解 KMP 是理解 AC 自动机的基础两者一脉相承。7.3 生物信息学中的短序列匹配DNA 序列只有 A、T、C、G 四种字符长度常常是数百万级。在这种小字符集、超长文本的场景下KMP 这种无回溯匹配非常适用。当然更专业的工作会用到了后缀数组、FM-index 这些更进阶的算法但 KMP 仍然是理解这些高级工具的入门阶梯。7.4 流式数据匹配某些场景下你没法一次性拿到整个文本比如网络数据包内容过滤。文本是流式到达的不能用indexOf但你可以用 KMP 的自动机思想维护一个“当前匹配到模式串第几位”的状态变量每来一个字符更新状态状态达到 m 即算命中。这个思路也叫“流式 KMP”非常实用。我自己写过一个小工具就是从实时日志流里筛出特定日志模式并触发告警用的就是流式 KMP。好处是内存占用恒定只需要保存模式串和 next 数组处理速度跟得上每秒几十万条日志完全不用缓冲整个文本。KMP 还有一种有意思的扩展叫字符串的循环节问题。比如判断字符串是否由某个子串重复构成LeetCode 459 那种题本质上就是利用 next 数组的末位值如果n % (n - next[n-1]) 0那么循环节长度为n - next[n-1]。这个技巧当年第一次见到时有种“原来 next 数组还能这样用”的感觉。8. 一些实际的测试与体会文章写到这里还是要回到实践层面分享几个我从写代码到调 bug 过程中积累的感受。第一KMP 的代码本身非常短几十行就写完了。但理解它比写出来更重要。面试时如果只是背出模板被问到 “next 数组为什么能这样跳” 就会露馅。我的做法是手画匹配过程自己在草纸上把每次 j 跳转的前因后果画出来。画过两边之后你会发现KMP 没有想象中那么玄它就是一个充分利用已知信息的线性扫描算法。第二调 bug 时最有效的工具是“打印”。给buildNext加上逐步打印 i、j、next 数组的 log然后拿一个短模式串手跑几乎任何 bug 都能马上定位。比单步调试快得多。第三如果实际项目的文本绝大多数是 ASCII 字符且模式串固定不变KMP 的性能很好。但如果是短文本几十个字符里的短模式串几个字符暴力匹配的常数开销更低KMP 不一定占优。算法选型不是 “最高级的就一定最好”要结合数据规模权衡。第四也是我踩得最实的一次坑用 KMP 处理超大文本时发现内存占用高于预期。原因是我用charAt后Java 的 char 是 UTF-16对于 BMP 之外的 emoji 字符一个 char 存不下匹配结果会错位。后来改成按码点处理用Character.codePointAtCharacter.charCount推进索引问题才解决。做中文和 emoji 相关的匹配任务时这点一定要留意。KMP 这个算法从提出到现在快半个世纪了依然活跃在各种系统和算法题里。它教会我的核心思想其实一句话就能概括已经比对过的信息不该被浪费。这个原则不仅在算法里成立在工程设计和性能优化里同样适用。以后遇到类似 “重复计算太多次” 的问题不妨停下来想一想是不是可以像 KMP 一样把之前得到的结果复用起来