企业官网建设流程全解析

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(n+m) 的算法，而且思路还挺巧妙。

这篇文章就专门把 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] 的最大相等前后缀的长度

比如模式串"ABABCA"：

next 数组构建完成后，匹配过程在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]能不能让这个匹配继续延伸。

具体的递推逻辑这样理解：

1. 设j = next[i-1]，也就是P[0..i-1]的最大相等前后缀长度。这时候P[0..j-1]与P[i-j..i-1]是相同的。
2. 比较P[i]和P[j]：
   • 如果相等，那么P[0..i]的最大相等前后缀就是j+1，即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"，会用这种右移版 next：

• i=0, j=-1：进入j==-1分支，i=1, j=0, next[1]=0
• i=1, j=0：P[1]=B，P[0]=A，不相等，j=next[0]=-1
• i=1, j=-1：进入j==-1分支，i=2, j=0, next[2]=0
• i=2, j=0：P[2]=A，P[0]=A，相等，i=3, j=1, next[3]=1
• i=3, j=1：P[3]=B，P[1]=B，相等，i=4, j=2, next[4]=2
• i=4, j=2：P[4]=C，P[2]=A，不相等，j=next[2]=0
• i=4, j=0：P[4]=C，P[0]=A，不相等，j=next[0]=-1
• i=4, j=-1：进入j==-1分支，i=5, j=0, next[5]=0
• i=5, j=0：P[5]=A，P[0]=A，相等，i=6, j=1，循环结束（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"来演示：

第一阶段（前面都比较顺利）：

关键在第 5 步：文本串第 4 位是A，模式串第 4 位是C，失配。暴力匹配会直接把文本串指针回退到 1，重新来。KMP 呢？j跳到2，意味着模式串的"AB"前缀直接对齐了文本串刚匹配过的"AB"后缀，不用回退文本串。

第二阶段（利用 next 跳转后）：

j == 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 List<Integer> findAll(String text, String pattern) { List<Integer> 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(n+m)，空间复杂度 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 数组主要有两类：

两种都能跑通，但混用就会出 bug。比如你把 PMT 版概念的 next 值直接塞进右移版的匹配代码里，边界条件全乱。我建议选一种记住，理解透它的下标含义，另外那种知道存在即可。

6.2 模式串为空

工程中文本查找，模式串为空字符串时应该返回什么？一般返回 0（表示空串在任何位置都能匹配）。很多实现没处理这个边界，直接buildNext里m=0时数组长度 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 文本编辑器的查找功能

文本编辑器里按 Ctrl+F 查找关键词，底层就是某种字符串匹配算法。对于超大文件（几百 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.codePointAt+Character.charCount推进索引），问题才解决。做中文和 emoji 相关的匹配任务时，这点一定要留意。

KMP 这个算法，从提出到现在快半个世纪了，依然活跃在各种系统和算法题里。它教会我的核心思想其实一句话就能概括：已经比对过的信息不该被浪费。这个原则不仅在算法里成立，在工程设计和性能优化里同样适用。以后遇到类似 “重复计算太多次” 的问题，不妨停下来想一想：是不是可以像 KMP 一样，把之前得到的结果复用起来？