企业官网建设流程全解析

字符串匹配是写程序时绕不开的活，从文本编辑器里的查找替换，到日志系统里过滤关键词，再到生物信息里比对DNA片段，本质上都在做同一件事：给定一个主串和一个模式串，找出模式串在主串中的位置。KMP算法就是解决这个问题的经典方案，全称是Knuth-Morris-Pratt算法，由三位计算机科学家在1977年联合提出。很多人第一次接触它是在数据结构课上，但真正把它用明白、能手写出来，往往要等到实际写代码踩过几次坑之后。这篇内容围绕KMP算法的核心——next数组展开，重点手算一个具体例子：模式串p="abacaba"的next数组到底怎么求，以及求出来之后如何驱动整个匹配过程。

我尽量用实际写代码的视角来讲，不堆公式，把每一步为什么这么做讲清楚。适合正在学数据结构的同学、准备算法面试的开发者，以及那些学过KMP但总感觉“懂了又没完全懂”的人。

1. 暴力匹配的问题与KMP的核心思想

1.1 暴力匹配为什么慢

先看最直观的暴力匹配思路。假设主串s长度为n，模式串p长度为m，做法是让模式串从主串的每个位置开始对齐，然后逐个字符比较，全部匹配就返回位置，中途失配就整体右移一位，重新比较。

def brute_force(s, p): n, m = len(s), len(p) for i in range(n - m + 1): j = 0 while j < m and s[i + j] == p[j]: j += 1 if j == m: return i return -1

这个代码很好理解，但性能隐患很大。考虑一个极端场景：主串是"aaaaaaaaaaaaaaaaaaaaaaaaaab"，模式串是"aaaaab"，每次匹配都要比较到模式串最后一个字符才发现b不匹配，然后主串指针只前进一位，又来一遍。整体时间复杂度是O(n*m)，主串和模式串一长，程序就肉眼可见地卡顿。

暴力匹配浪费在哪里？浪费在那些“已经比较过的、匹配成功的信息”上。主串第i位开始匹配时，前面已经确认s[i..i+j-1]等于p[0..j-1]，这部分信息是花了时间比较出来的，但当p[j]失配时，暴力做法直接放弃这一整段信息，把模式串挪一位从头比。实际上，我们已经知道主串这一段长什么样了，完全可以用这个信息来决定模式串跳到哪个位置更合理。

1.2 KMP的一句话核心

KMP算法的核心思想非常朴素：当模式串在第j个位置失配时，不要简单地右移一位，而是根据模式串自身的结构，把模式串指针j回退到一个合适的位置，主串指针i不回退。这样主串从头到尾只需要扫描一遍，时间复杂度从O(n*m)降到了O(n+m)。

那“合适的位置”怎么确定？这就要看模式串失配位置之前的子串，它的前缀和后缀有多少是重合的。举个例子，模式串"abacaba"在最后一个'a'失配时，前面"abacab"已经匹配成功了，如果"abacab"有一个较长的前缀和后缀相等，那我们就能把这个前缀挪到刚才后缀的位置上，因为这些字符已经被主串验证过了，不需要重新比较。

这个“失配时回退到哪里”的信息，就是提前预处理出来的next数组。理解了这一点，KMP就不再是死记硬背的代码模板，而是一个逻辑上非常顺其自然的优化方案。

2. next数组的定义与手算：以p="abacaba"为例

2.1 next数组想表达什么

next数组的经典定义是：对于模式串p，next[i]表示当p[i]与主串字符失配时，模式串指针i应该回退到的位置。换句话说，回退位置取决于p[0..i-1]这段已经匹配成功的子串中，最长相等前后缀的长度。

这里有两个概念必须先拆清楚：“前缀”和“后缀”。前缀是指从子串第一个字符开始、但不包含最后一个字符的任意连续子串；后缀是指以子串最后一个字符结尾、但不包含第一个字符的任意连续子串。比如子串"abac"，它的前缀有"a"、"ab"、"aba"，后缀有"c"、"ac"、"bac"，前后缀相等的只有长度0，也就是说没有任何相同的前后缀。

如果子串"abab"，前缀有"a"、"ab"、"aba"，后缀有"b"、"ab"、"bab"，相等的有"a"和"ab"，最长相等前后缀长度是2。这个“最长相等前后缀”就是next数组的核心素材，它告诉我们：当这一段匹配成功后遇到失配，模式串可以直接把前缀挪到后缀的位置上，不用回到开头。

2.2 手算p="abacaba"的next数组

现在手算题目里这个具体的模式串。p = "abacaba"，下标从0开始，位置分别是：0='a'，1='b'，2='a'，3='c'，4='a'，5='b'，6='a'。

我按照“next[i] = p[0..i-1]的最长相等前后缀长度”这个定义来算，这也是最常见的数据结构教材定义。逐个位置推一遍：

• next[0]：p[0]之前没有字符，是一个特殊位置，约定为-1，代表模式串已经无法再回退，需要主串指针前移。
• next[1]：看p[0..0]="a"，只有一个字符，没有真正的前缀和后缀，最长相等前后缀长度为0。
• next[2]：看p[0..1]="ab"，前缀有"a"，后缀有"b"，不相等，长度为0。
• next[3]：看p[0..2]="aba"，前缀有"a"、"ab"，后缀有"a"、"ba"，相等的只有"a"，长度为1。
• next[4]：看p[0..3]="abac"，前缀"a"、"ab"、"aba"，后缀"c"、"ac"、"bac"，没有相等的，长度为0。
• next[5]：看p[0..4]="abaca"，前缀"a"、"ab"、"aba"、"abac"，后缀"a"、"ca"、"aca"、"baca"，相等的只有"a"，长度为1。
• next[6]：看p[0..5]="abacab"，前缀"a"、"ab"、"aba"、"abac"、"abaca"，后缀"b"、"ab"、"cab"、"acab"、"bacab"，相等的最长的是"ab"，长度为2。

整理成表格：

所以p="abacaba"的next数组是[-1, 0, 0, 1, 0, 1, 2]。这是按“失配时模式串指针回退到next[i]”的定义来的，也是最常见的写法。

2.3 另一种定义与换算

这里必须多说一句，因为next数组在不同教材、不同文章里定义差异很大，特别容易把人搞晕。我见过至少三种：

第一种就是我上面用的：next[i]表示p[0..i-1]的最长相等前后缀长度，next[0]=-1，失配时i回退到next[i]。C语言风格的教材和大部分考研资料用这种。

第二种：next[i]表示p[0..i]的最长相等前后缀长度，next[0]=0，失配时i回退到next[i-1]。这种写法的代码更统一，但要特别小心边界。用这种定义算p="abacaba"，结果是[0, 0, 1, 0, 1, 2, 3]，和第一种定义相比整体错了一位。

第三种：从下标1开始存储，next[1]=0，next[j]表示p[0..j-2]的最长相等前后缀长度再加1。这是严蔚敏版数据结构教材的写法，面试时偶尔会遇到。

我的建议是：自己写代码时认准一种定义，把对应的匹配逻辑写对就行；读别人的文章时先看它的初始化和失配回退代码，反推它用的是哪种定义，不要拿A定义的数组去套B定义的匹配逻辑。否则结果对不上，还以为是自己算错了。

3. 递推求解next数组：原理与代码

3.1 为什么可以递推

求next数组如果每个位置都从头数一遍前缀后缀，那复杂度又回到O(n*m)了，得不偿失。KMP的精髓在于，next数组本身也可以递推得到。

假设我们已经知道next[0..i-1]的值，现在要求next[i]。注意next[i]描述的是p[0..i-1]的最长相等前后缀长度，它其实和next[i-1]描述的对象有关系。如果p[i-1] == p[next[i-1]]，那说明在上一段最长相等前后缀的基础上，后面又续上了一个字符，所以next[i] = next[i-1] + 1。

如果字符不相等呢？那就不能直接续上了，需要退一步，找更短的相等前后缀。这个“退一步”不是随便退，而是退到next[next[i-1]]的位置，因为这个位置记录了更短的前缀信息。这个过程可能会循环几次，直到找到相等的字符，或者退到-1（或0，取决于定义）为止。

这个递归式的回退逻辑，是整个KMP算法里最绕的地方。我当初学的时候也是在这个地方卡了很久。用一句话总结：next数组的求解，本质上是在用KMP的思想自己匹配自己，模式串既是主串又是模式串。

3.2 完整代码

我用Python写一版完整的next数组求解，采用2.2节的定义，失配时i回退到next[i]：

def build_next(p): m = len(p) nxt = [-1] * m i, j = 0, -1 while i < m - 1: if j == -1 or p[i] == p[j]: i += 1 j += 1 nxt[i] = j else: j = nxt[j] return nxt

这段代码很短，但每一行都有讲究。i是当前要计算next的位置，j记录的是上一个位置的next值，也就是当前已匹配的前缀长度。当p[i] == p[j]时，说明最长相等前后缀可以延长一位，于是i和j各前进一位，nxt[i]就是新的j。当字符不相等时，j回退到nxt[j]，继续尝试更短的前缀。如果j回退到-1，说明没有任何相等前后缀，nxt[i]直接是0。

这个写法虽然有-1这个特殊值，但逻辑非常统一，配合2.2的定义用起来很顺手。验证一下，p="abacaba"时，运行结果就是[-1, 0, 0, 1, 0, 1, 2]。

3.3 代码里的几个关键细节

写这段代码时容易出问题的点，我挨个说一下。

第一个：while循环的边界是i < m-1，不是i < m。因为循环体里i会先自增再赋值，最后一次循环i自增后已经是最后一个下标m-1，不需要也不应该再计算nxt[m]（字符串最后一个位置之后已经没有字符了）。如果写成i < m，数组就越界了。

第二个：nxt[0]必须单独初始化为-1，这是整个回退链的终点。如果没有这个-1，当j回退到无路可退时，代码会陷入死循环。很多初学KMP的人在这里出问题，就是没有理解-1这个哨兵的作用。

第三个：这个版本求出来的是“基础版next数组”，没有做优化。模式串中如果有大量重复字符，比如"aaaaab"，基础版next数组在某些场景下会多做几次无意义的回退。优化版通常叫nextval，在p[i] == p[nxt[i]]时继续回退，把指针直接指向最终有效的跳跃位置。面试如果问KMP优化，基本都是问这个。建议先把基础版吃透，再看优化版，否则容易两套逻辑混在一起。

4. 完整匹配流程与复杂度分析

4.1 匹配主流程代码

有了next数组，匹配过程就非常简单了。两个指针，i遍历主串，j遍历模式串，主串指针永不回头：

def kmp_search(s, p): n, m = len(s), len(p) if m == 0: return 0 nxt = build_next(p) i, j = 0, 0 while i < n: if j == -1 or s[i] == p[j]: i += 1 j += 1 if j == m: return i - m else: j = nxt[j] return -1

匹配过程中，如果s[i]和p[j]相等，两个指针同时前进；如果不相等，j回退到nxt[j]；如果j已经回退到-1，说明模式串的头部都对不上当前主串字符，此时i前进一位，j恢复为0。j==m说明模式串完整匹配成功，返回起始位置。

来模拟一遍。主串s="ababacabacaba"，模式串p="abacaba"，nxt=[-1,0,0,1,0,1,2]。

i=0时，s[0]='a'，p[0]='a'，匹配，i=1，j=1。i=1时，s[1]='b'，p[1]='b'，匹配，i=2，j=2。i=2时，s[2]='a'，p[2]='a'，匹配，i=3，j=3。i=3时，s[3]='b'，p[3]='c'，失配，j=nxt[3]=1，此时模式串从位置1开始继续比。i=3时，s[3]='b'，p[1]='b'，匹配，i=4，j=2。i=4时，s[4]='a'，p[2]='a'，匹配，i=5，j=3。i=5时，s[5]='c'，p[3]='c'，匹配，i=6，j=4。之后一路匹配到i=9，j=7，j==m，返回9-7=2。p="abacaba"从主串下标2开始确实匹配。

4.2 时间复杂度分析

KMP的时间复杂度是O(n+m)，这个结论很多人知道，但不知道为什么。关键在于：主串指针i在整个匹配过程中只会增加，从不回退，所以遍历主串的代价是O(n)。而模式串指针j虽然会回退，但每次回退都是通过next数组跳转，跳转次数不会超过匹配成功的总次数，整体也是O(m)级别。两者加起来就是O(n+m)。

空间复杂度是O(m)，主要花在next数组上。相比暴力匹配的O(1)空间，多付出了一个模式串长度级别的数组，但对于m通常不会太大的实际场景来说，这个代价完全可接受。如果模式串很短，或者主串和模式串长度差异极大，暴力匹配的常数项反而更小，KMP的优势主要体现在模式串较长、且主串中频繁出现部分匹配的场景。实际工程里像grep这类工具，还会结合Boyer-Moore或Sunday等更快的算法，但对于理解字符串匹配的核心思想来说，KMP是绕不开的基础课。

5. 常见问题与排查

5.1 最容易踩的坑

第一个坑：next数组定义没对上，匹配代码直接套用。这是最常见的翻车现场。网上搜KMP代码，有的用next[0]=-1，有的用next[0]=0，有的数组长度是m，有的是m+1，失配回退时有的写j=next[j]，有的写j=next[j-1]。这些代码本身可能都是对的，但混着用就全乱了。我建议把一份代码从头到尾吃透，包括它用的定义、初始化、回退逻辑，然后固定下来，其他写法只作为理解参考，不要混搭。

第二个坑：模式串长度为0或1的边界情况。长度为0时直接返回0，长度为1时，如果匹配到就返回位置，匹配不到返回-1，next数组只需要处理nxt[0]=-1。很多KMP实现忽略了这些边界，实际跑起来就报越界。

第三个坑：返回位置的计算。匹配成功返回的是i-m，因为当j==m时，i已经走到了模式串结束位置的后面，起始位置是i减去模式串长度。有人会写成i-j，这在某些特殊时候碰巧对，但逻辑上不对，因为j此时等于m，i-j等价于i-m，但如果中途有回退，i-j就不是起始位置了。

第四个坑：求next数组时误用了m而不是m-1作为循环边界。这个问题我在3.3节已经提过，这里再强调一次，它导致的数组越界问题在刷题平台上很容易遇到。

5.2 快速排查表

排查时最有效的办法是拿着小例子手推一遍，代码逻辑对不对一目了然。别上来就在大数据集上跑，那样只能看到结果错，看不到错在哪一步。

5.3 一个提高效率的小技巧

实际写代码时，如果模式串是固定不变的，可以把build_next的结果缓存下来，避免每次匹配都重新计算。这个优化在处理多段文本搜索同一个关键词时特别明显。另外，Python里如果你只是想找一个子串，直接用in或find就好，内置算法已经很快，手写KMP主要用于学习和理解原理，或者在某些不能调用内置函数的场景下使用。

nextval优化版我也简单提一下，它在求next的过程中，如果发现p[i] == p[next[i]]，就把next[i]继续往前跳，直到跳到不同的字符为止。这样做的好处是，匹配阶段遇到重复字符时能一次跳到位，减少无意义的字符比较。代价是预处理阶段多了一点计算，但整体收益在模式串重复度高的场景下非常明显。面试题里如果考KMP优化，基本就是考这个nextval的构造。

我自己的体会是，KMP算法第一次学的时候觉得很玄，本质上就是把“模式串的自相似性”这张表提前算好，用空间换时间。一旦你把next数组的递推过程想明白了，后续再看任何字符串匹配算法都会轻松很多。