企业官网建设流程全解析

字符串匹配这件事，只要写过一点数据处理代码的人基本都绕不开。日志里筛关键字、编辑器里找函数定义、甚至基因序列比对，本质都是在做同一件事：在主串里找模式串。暴力解的思路人人都能秒懂，可一旦主串和模式串里堆满重复前缀，那种“匹配到一半被打回起点”的滋味实在折磨人。KMP 的价值，就是把这种搜索从 O(m*n) 拉到了 O(m+n)，核心就是那张看起来毫不起眼的 next 数组。

这篇文章接着系列往下聊，重点放在 next 数组到底是怎么构建出来的、两套主流语义怎么区分、匹配主流程怎么一步步推演，以及我实际写代码时踩过的那些坑。如果你刚接触 KMP，建议先把暴力匹配和“前后缀”这两个概念在纸上过一遍；如果已经写过几版 KMP，可以直接跳到第 5 节看调试经验，那部分基本是文档里不会写的东西。

1. 先搞清楚 next 数组到底在解决什么问题

KMP 难理解，主要不是代码复杂，而是很多人还没想明白 next 数组的“位置”。它不是一个锦上添花的优化，而是整个算法的地基。这一节先把地基说透。

1.1 暴力匹配到底浪费在哪

暴力匹配的思路是：主串从第 0 位开始，模式串也从头开始，一个一个比。一旦字符对不上，抱歉，主串指针回到上次起点的下一位，模式串指针清零，全部重来。

举个例子。主串是aabaabaaf，模式串是aabaaf。暴力匹配会从主串第 0 位开始对齐，前 5 个字符aabaa都能对上，第 6 个字符主串是b，模式串是f，失配。于是主串指针挪到第 1 位，模式串又从a开始。这个场景里真正尴尬的是：上一轮我们已经辛苦确认了aabaa完全匹配，这些信息在这一刻被全部丢弃，然后主串继续一格一格挪，模式串继续从头开始，重复劳动相当明显。

越是在模式串里频繁出现“相同前缀”的输入，暴力匹配的浪费就越严重。比如在主串aaaabaaaaaaa里找aaaa，每一步几乎都在做相似的比对，一步失配就全盘推倒，实际开销接近 O(m*n)。

KMP 的核心洞察其实很朴素：既然模式串和主串已经匹配了一段前缀，那么这段前缀的内部结构（有哪些“两头一样”的部分）是可以提前算好的。失配发生时，我不需要把主串指针退回起点，也不需要让模式串指针回到 0，只需要根据预先算好的信息，把模式串“滑动”到一个合理的位置继续比。

这个“合理的位置”，就是 next 数组给出的。

1.2 最长相等前后缀是怎么救场的

要理解 next 数组，必须先接受一个概念：最长相等前后缀。

一个字符串的前缀，是从开头开始、但不包含最后一个字符的连续子串；后缀是从末尾开始、但不包含第一个字符的连续子串。以aabaa为例，它的前缀有a、aa、aab、aaba，后缀有a、aa、baa、abaa。前后缀都出现的最大公共部分是aa，长度为 2，所以aabaa的最长相等前后缀长度就是 2。

注意一个微妙之处：最长相等前后缀不能等于字符串本身。因为如果允许“整串等于整串”，那每个字符串的最长相等前后缀都是它自己，失配时算出来的回退位置等于没退，算法就把信息浪费光了。所以只能是“真前缀”和“真后缀”的比较。

那么这个值对失配有帮助吗？有帮助。假设模式串aabaaf和主串匹配到了aabaa，主串第 5 位是b，模式串第 5 位是f，失配。此时模式串的前 5 个字符aabaa已经确认和主串的 5 个字符一致。aabaa的最长相等前后缀是长度 2 的aa，那么我完全可以确定：主串当前位置的前 2 个字符，也一定是aa。于是模式串不需要从头对齐，只需要把模式串的 2 号位对齐过来继续比。

这就是 KMP 一劳永逸的本事：主串指针永远不回头，顶多是在原地多比较两次；需要调整的只是模式串内部的指针位置。而所有模式串内部的“撤退方案”，都被提前写进 next 数组里，匹配的时候照着执行就行。

2. next 数组的构建：原理、两套语义与手写推演

next 数组是 KMP 的灵魂，但不同书、不同教程对 next 的定义略有差异，初学者很容易被绕晕。我先把最常见的两套语义摆出来，再给出一套可直接上手的代码，最后手推一个完整例子。

2.1 最长相等前后缀的计算规则

无论哪种语义，计算核心都是那两条规则：

• 如果当前字符和已匹配前缀的下一个字符相同，就在上一个结果上加 1；
• 如果不同，就沿着已经算好的 next 值往前回退，回退到不能再回退为止；
• 如果回退到 0，说明当前字符没有可利用的相等前后缀，记为 0。

这个过程本质上就是“模式串自己和自己匹配”。你甚至可以理解为：构建 next 数组，就是用模式串去匹配它自己的一个前缀匹配过程。

以字符串ababcab为例，我用人肉推演走一遍，这样比你直接看代码更直观：

• 第 0 位：a，前后缀都为空，next[0] = 0；
• 第 1 位：ab，前缀a，后缀b，不等，next[1] = 0；
• 第 2 位：aba，前缀a、ab，后缀ba、a，最长相等前后缀是a，长度 1，next[2] = 1；
• 第 3 位：abab，前缀a、ab、aba，后缀bab、ab、b，最长相等前后缀是ab，长度 2，next[3] = 2；
• 第 4 位：ababc，逐项比较后发现没有可用的相等前后缀，next[4] = 0；
• 第 5 位：ababca，只发现单个字符a相等，next[5] = 1；
• 第 6 位：ababcab，最长相等前后缀是ab，长度 2，next[6] = 2。

这样得到的 next 数组是[0, 0, 1, 2, 0, 1, 2]。你可以注意到，next[i] 在这里表示：以第 i 位结尾的整个前缀子串，它的最长相等前后缀长度是多少。这是当前最主流的一种语义，后面代码都用这个。

2.2 主流写法：以“0 到 i 的最长相等前后缀”为语义

基于上面的语义，构建代码可以写成下面这样，我用 Java 写，换成 C/C++ 只是换个语法的事：

public int[] buildNext(String p) { int n = p.length(); int[] next = new int[n]; int j = 0; // j 同时代表已匹配的前缀长度，也代表当前前缀的下标 next[0] = 0; for (int i = 1; i < n; i++) { // 字符不匹配时，沿 next 回退 while (j > 0 && p.charAt(i) != p.charAt(j)) { j = next[j - 1]; } // 匹配成功，前缀长度 +1 if (p.charAt(i) == p.charAt(j)) { j++; } next[i] = j; } return next; }

这一段代码最容易被问到的有两个地方。

第一个是while循环里为什么是j = next[j - 1]，而不是j = next[j]。因为j在循环里的含义是“已匹配前缀的长度”，不是下标。p.charAt(j)比较的其实是“下一个待匹配的字符”。如果失配，我们希望回退到“当前已经匹配成功的这段前缀”的最长相等前后缀位置，这个位置正好是next[j - 1]。你要是写成next[j]，语义就彻底错位了，回退后还可能越界。

第二个是为什么j == 0时不再回退。因为当j == 0，说明没有前缀可用了，只能老老实实把当前字符跟模式串第 0 位比较；再回退就成next[-1]，程序直接崩溃。这个边界条件写代码时非常容易漏。

这里还有个小细节：p.charAt(i) == p.charAt(j)的判断在j == 0时一定要放在while之后执行，否则你连“当前字符跟前缀首字符能否匹配”都没有机会比较。很多新手写成if在前、while在后，结果 next 数组怎么算都不对。

2.3 手动推演一个完整的 next 数组

拿ababcab来跑一遍代码逻辑，正好和前面手推的结果对上。

• 初始：i = 1，j = 0。比较p[1] = 'b'和p[0] = 'a'，不等，next[1] = 0；
• i = 2，j = 0。比较p[2] = 'a'和p[0] = 'a'，相等，j变成 1，next[2] = 1；
• i = 3，j = 1。比较p[3] = 'b'和p[1] = 'b'，相等，j变成 2，next[3] = 2；
• i = 4，j = 2。比较p[4] = 'c'和p[2] = 'a'，不等，于是j = next[1] = 0；再次比较p[4] = 'c'和p[0] = 'a'，不等，next[4] = 0；
• i = 5，j = 0。比较p[5] = 'a'和p[0] = 'a'，相等，j变成 1，next[5] = 1；
• i = 6，j = 1。比较p[6] = 'b'和p[1] = 'b'，相等，j变成 2，next[6] = 2。

结果还是[0, 0, 1, 2, 0, 1, 2]。这组数据后面匹配主流程还会复用，建议你在纸上自己推一遍，亲眼看到i一路向右、j来回跳跃，比看任何讲解都管用。

2.4 另一种语义：next[i] 表示 0 到 i-1 的最长相等前后缀

网上有些教材和资料用的是另一套定义：next[i]表示“以第 i-1 位结尾的前缀”的最长相等前后缀长度，并且把next[0]设为 -1。这其实来自国内经典数据结构教材里的写法，代码风格也略有不同，我见过很多同学两套混着记，越记越乱。

那套写法的构建逻辑长这样：

public int[] buildNextV2(String p) { int n = p.length(); int[] next = new int[n]; next[0] = -1; int i = 1, j = 0; while (i < n) { if (j == -1 || p.charAt(i) == p.charAt(j)) { i++; j++; next[i] = j; } else { j = next[j]; } } return next; }

这套代码里的j含义也是“已匹配前缀长度”，但因为next[0] = -1，所以失配回退公式变成了j = next[j]，并且需要专门判断j == -1。这种设计在某些场景下写起来对称，但对初学者来说，一是多了一个 -1 的魔法值，二是容易和上一套混淆。我自己在实际编码里更推荐第 2.2 节那套，因为：

• 全程没有 -1，边界更好理解；
• 匹配主流程里失配回退统一用next[j - 1]，跟构建逻辑保持一致；
• 在线OJ和大多数面试手写代码都偏爱这套，资料好找。

两套语义没有高下之分，但你自己心里必须钉死一套，不能一会儿用这套一套，一会儿用那套。我见过不少人背模板背串了，构建用的是定义 B，到匹配时却套定义 A 的回退公式，结果怎么调都不对，最后连 next 数组都对不上号。选一套，从头到尾只认这一套，比什么都重要。

3. 匹配主流程：代码实现与完整实例推演

next 数组准备好了，匹配主流程反而简单。核心思路就是：主串指针i从 0 走到m-1，一次都不回头；模式串指针j根据 next 数组回退。整个过程中，模式串相对主串不断“滑动”，但主串永远只被读一遍。

3.1 匹配函数怎么写

直接上代码：

public int kmpSearch(String text, String pattern) { if (pattern.length() == 0) { return 0; } int[] next = buildNext(pattern); int j = 0; for (int i = 0; i < text.length(); i++) { // 失配时回退，直到 j 回到 0 或字符匹配 while (j > 0 && text.charAt(i) != pattern.charAt(j)) { j = next[j - 1]; } if (text.charAt(i) == pattern.charAt(j)) { j++; } // 完全匹配，返回起始位置 if (j == pattern.length()) { return i - pattern.length() + 1; } } return -1; }

这段代码有三个关键点。

第一，while (j > 0 && text.charAt(i) != pattern.charAt(j))里的j > 0是必须的。当j == 0且当前字符和模式串首字符不匹配时，只能让i继续前进，否则访问next[-1]直接越界。这个条件也是很多初学者程序崩溃的根源。

第二，为什么失配时回退j = next[j - 1]，而不是让i回头。因为 next 数组已经保证了：模式串里[0, j-1]这部分已经在主串的对应位置匹配成功，而这段子串的前后缀信息在 next 里，回退不会丢信息。你只要把模式串滑过去，让模式串的前缀部分对齐主串已经验证过的后缀部分就行。

第三，匹配成功的判断要放在字符比较之后，别放反了。j每加一次，都要立刻检查是否已经达到模式串长度，否则下一个text.charAt(i)和pattern.charAt(j)的j就越界了。

3.2 一次完整的失配回退过程

用一个具体例子走一遍，数据就用前面算好 next 的ababcab。

主串：abababcab，模式串：ababcab，next =[0, 0, 1, 2, 0, 1, 2]。

• i = 0，j = 0：a == a，j变成 1；
• i = 1，j = 1：b == b，j变成 2；
• i = 2，j = 2：a == a，j变成 3；
• i = 3，j = 3：b == b，j变成 4；
• i = 4，j = 4：主串是a，模式串是c，失配。此时j > 0，执行j = next[3] = 2；继续比较主串a和模式串pattern[2] = 'a'，相等，j变成 3；
• i = 5，j = 3：主串b，模式串pattern[3] = 'b'，相等，j变成 4；
• i = 6，j = 4：主串c，模式串pattern[4] = 'c'，相等，j变成 5；
• i = 7，j = 5：主串a，模式串pattern[5] = 'a'，相等，j变成 6；
• i = 8，j = 6：主串b，模式串pattern[6] = 'b'，相等，j变成 7；
• 此时j == pattern.length()，返回8 - 7 + 1 = 2。

注意第 5 步的关键行为：主串指针i没有回退到第 3 位，而是继续从第 4 位往后走；模式串指针从 4 回退到 2，再通过一次比较前进到 3。匹配结果和暴力解一致，但主串只扫描了一遍。

如果你自己跑这段推演，会发现第 5 步能顺利成立的前提，正是abab这个子串的最长相等前后缀为ab（长度 2）。失配发生在模式串第 4 位，我只需要从它的第 2 位继续比，因为ab已经作为前缀被验证过。这个“因为确认了部分匹配，所以可以安全滑动”的逻辑，是 KMP 的核心，也是 next 数组的价值所在。

3.3 时间复杂度为什么是 O(m+n)

很多人背结论：KMP 是 O(m+n)，但不理解为什么。这里给一个比较直观的论证思路。

先看构建 next 的过程。外层循环里i从 1 走到n-1，一共 n-1 次；内层while每执行一次，j都会变小，而j总共只可能被外面的if增大 n-1 次。也就是说，j减少的总次数不可能超过增加的总次数，均摊到每次循环，每次回退的代价是 O(1)。所以构建 next 的总时间是 O(n)。

再看匹配过程。主串指针i从 0 走到m-1，一次不回头，外层循环最多执行 m 次；模式串指针j有增有减，但j的每次增加都对应一次外层循环（i前进一格），而j减少的次数不会超过增加次数，所以回退总次数是 O(m)。匹配阶段的整体复杂度就是 O(m)。

两者相加就是 O(m+n)。空间上只需要一个和模式串等长的 next 数组，O(n)。对超长文本做一次性搜索时，KMP 的优势非常明显，主串不会被反复回扫，这在流式处理和超大日志匹配场景下尤为重要。

4. KMP 的实战价值：从字符串查找到周期判断

KMP 不是一个只在考试题里出现的花架子算法，它在真实工程里有很多直接落地的用法。这一节挑两个最常见的场景展开，也顺便聊聊它和其它匹配算法的取舍。

4.1 在真正的工程代码里它怎么用

很多人以为标准库里有现成的匹配函数，KMP 是不是就没用了。其实要看场景。Java 的String.indexOf在模式串较短时用的是朴素算法加上一些针对性优化，但在处理大文本、模式串又很长、重复性又强时，朴素解的性能会明显劣化。我在处理几 MB 的日志文本时做过对比，同样的模式和样板子，KMP 的耗时能比朴素解低一个数量级，尤其是在模式串前缀重复很严重的情况下。

大规模文本的批量筛选、DNA 序列中查找特定片段、文本编辑器的增量搜索，这些都是 KMP 的典型落地场景。你不需要每次自己实现，但当你需要优化搜索性能、又不想引入太重的外部组件时，手写一个 KMP 往往是最干净的选择，代码不过几十行，没有任何依赖，也容易剪裁成适合自身业务的模样。

KMP 还经常作为其它更复杂算法的“底座”出现。比如自动机相关的匹配框架、正则表达式的某些底层匹配路径，都会沿用“预处理模式串 + 线性扫描主串”这一思想。能把 KMP 的核心逻辑吃透，后面学更复杂的字符串算法会顺很多。

4.2 用 next 数组判断重复子串

KMP 除了直接查匹配位置，还有一个非常实用的衍生用法：判断一个字符串是否由某个子串重复构成。

先说结论：如果字符串长度为 len，记next[len-1]为整个字符串的最长相等前后缀长度，那么当next[len-1] > 0且len % (len - next[len-1]) == 0时，这个字符串就能由长度为len - next[len-1]的子串重复构成。

举个例子，ababab，长度 6。对ababab构建 next 数组，得到[0, 0, 1, 2, 3, 4]，next[5] = 4，那么最小周期len - next[5] = 2，并且6 % 2 == 0，所以它由ab重复三次构成。再看ababc，next 数组是[0, 0, 1, 2, 0]，next[4] = 0，不满足大于 0 的条件，直接判断为不是重复子串构成。

这里有个非常隐蔽的坑：如果漏掉next[len-1] > 0这个条件，那么ab的len = 2、next[1] = 0，但你算出2 % (2 - 0) == 0，会误判成true。这个 bug 在逻辑上极难发现，因为你很难仅凭一个“由子串构成”的描述想起要检查这个前置条件。我自己就在这里吃过亏，写单测时 cover 了"abab"、"aabaab"这类用例，却漏了"ab"这种最短输入，上线后被同事一梭子打了回来。

这种求周期的方法还有一个变体场景：求解一个字符串的最小周期，或者统计它的重复次数。核心思路都是利用len - next[len-1]这个值。因为最长相等前后缀越接近整个字符串，说明字符串的“周期性”越强；如果没有相等前后缀，那这个字符串就不具备循环结构，只能认为周期为它本身。

4.3 与其它字符串匹配算法的取舍

KMP 不是字符串匹配的唯一答案，它在实际工程中还经常和另外两种算法摆在一起比较：BM 算法和 Sunday 算法。

BM 算法的思路是从右往左比较模式串，失配时利用“好后缀”和“坏字符”规则跳得更远。它在自然语言文本这类“字符分布均匀”的场景下，平均效率比 KMP 更高，很多文本编辑器的底层搜索用的就是 BM 的变体。但 BM 的预处理逻辑更复杂，代码量也大不少。

Sunday 算法是 BM 的简化版本，它的核心思路是：失配时直接看主串中“模式串末尾的下一个字符”，根据这个字符在模式串里的位置确定步长。Sunday 在大多数情况下跳得比 BM 还快，代码也短，但它属于平均性能优秀、最坏情况没有严格线性保证的算法。

那什么时候选 KMP？如果你需要严格的线性时间复杂度保证，比如处理 DNA 序列、解析协议报文，或者你的模式串非常长且重复度高，KMP 最合适。如果你要处理的是自然语言文本、追求平均速度，BM 或 Sunday 往往更实用。工程上没有“最好”的算法，只有“最匹配场景”的方案。能把 KMP 理透，再去看 BM 和 Sunday 会轻松很多，因为它们都是在“失配时如何利用已有信息跳得更远”这个思路上做文章。

5. 高频踩坑与调试经验实录

这一节是我最想写的内容。KMP 的代码短，但坑真的不少，而且很多坑不是语法错误，是语义混乱导致的。我把这几年看到和踩过的典型问题整理成了一张速查表，再讲一个补救调试流程。

5.1 五个最容易出错的点

这五条里，第一条是“元错误”，它会导致后面所有体验都不正常。就我观察，很多人是在背模板时没有区分教材版本：上午看的帖子用next[0] = 0、回退next[j - 1]，下午翻的书用next[0] = -1、回退next[j]，结果拼出来一个四不像，怎么跑怎么错。预防方法只有一个：写代码前，在注释里先写好“我的 next[i] 表示什么”，然后构建和匹配两段代码都用同一个注释约束自己。

还有一个很常见的理解偏差：把“最长相等前后缀”算成了包含整个字符串。比如abcab的最长相等前后缀是ab，长度 2，但有人会想“abcab本身也是前后缀”，硬算成 5，next 数组全错。记住：最长相等前后缀只能是真前后缀，不能等于字符串本身。如果你算出来的 next[n-1] 等于 n，那一定是在某个环节把整串也算进去了，排查时第一反应应该看这个。

5.2 推荐的调试流程

KMP 调试比普通算法麻烦，因为它出错时表面上是“匹配位置不对”，根因可能在 next 数组、可能在回退逻辑、也可能在边界条件，不按流程查很容易瞎忙。

我的调试流程是以下四步。

第一步，把 next 数组单独打印出来。这一步能过滤掉一大半问题。先找一个已知用例，比如模式串ababcab，手算 next 得到[0, 0, 1, 2, 0, 1, 2]，再让程序打印构建结果，对不上就说明构建阶段有问题，不用去排查匹配逻辑。如果手算不熟练，可以用一个更短的模式串，比如aab，next 应为[0, 1, 0]。

第二步，单独测试匹配流程，用一个带失配的典型主串。比如abababcab匹配ababcab，期望返回 2。如果返回 -1 或者位置不对，就在while回退那行加一行打印，输出当前的i、j、回退目标，和 3.2 节的手动推演逐行对照。看它到底是在哪一步算出的j和预期不一致。

第三步，边界用例覆盖。我常用的有一组：空模式串、模式和主串完全相同、模式串比主串长、模式串只有一个字符、模式串全部由同一字符组成（如aaaa）、主串里包含多个相同模式串。这些用例写成一个测试列表，每改一处代码重跑一遍。

第四步，如果还查不出问题，把 next 数组和标准实现逐位对比。很多时候问题出在“你以为代码语义正确，实际细微偏差”上。KMP 对语义极其敏感，一个j - 1写成j，错的往往不是一两位，而是整个数组错位，通过“打印逐位对比”就能一眼看到差异落在哪个位置，进而反推是哪个逻辑分支写岔了。

还有一个几乎所有文档都不会提的经验：构建 next 数组时建议在一个空项目里先验证对ababcab的输出，再投入业务代码。因为这个函数没有任何外部依赖，行为完全确定，单独验证的成本极低。如果连最小用例都过不了，后面的业务逻辑调试只会更绝望。

最后再分享一点个人体会

KMP 这套东西，代码量小得可怜，但理解成本确实不低。很多人卡在“next 数组为什么要倒着回退”这一步，我给朋友讲的时候常用一个比喻：这就像你在一个陌生的园区里找人，你手里有一张地图，标明了园区的重复格局，走岔了路不需要回大门口重新找，只要往后退到“上一处同样格局的位置”继续走就行。next 数组就是那张地图，而构建 next 数组的过程，相当于自己先把园区逛一圈、把格局画下来。

真把这个思想吃透了，你会发现在很多看似无关的问题里都能见到它的影子：状态机里的失败转移、编译原理里的 NFA 转 DFA、甚至某些缓存替换策略，本质上都共享“记录历史信息、避免重复计算”这一底层逻辑。我自己后来再看这些内容时，总有豁然开朗的感觉。

如果你正在学 KMP，我的建议是别急着刷题，先在纸上把ababcab的 next 数组手算三遍，再写代码验证，然后亲手跑一遍匹配回退过程。这个过程做完，你会觉得代码里的每一行都写得理所当然，而不是靠背。等你想通了，后面再做字符串匹配相关的题目，会轻松很多。