企业官网建设流程全解析

1. 为什么要学KMP：先看看暴力匹配到底浪费在哪

1.1 字符串匹配是日常开发里最不起眼的基本功

KMP这三个字母是谁的缩写不重要，重要的是它解决的那件小事——字符串匹配。别小看这件事，编辑器里的查找替换、日志系统里的关键字过滤、爬虫程序里的内容提取、文本处理里的模式定位，底层都绕不开它。你输入一段关键词，程序要在几万行文本里找出所有出现位置，背后跑的就是这一类的算法。

从定义上说，字符串匹配就是给定一个主串T，长度为n，再给一个模式串P，长度为m，我们要找P第一次出现在T里的起始下标。举个最简单的例子，T是“hello world”，P是“world”，匹配结果就是下标6。如果T里根本没有P，就返回-1或者一个约定好的值。

很多语言本身提供了查找函数，比如标准库里的字符串查找、正则表达式引擎等等，所以有人会觉得没必要自己实现。但理解KMP的真正价值有几个层面：第一，它是面试和算法考核里的常客，绕不过去；第二，它把最坏时间复杂度从O(n*m)降到了O(n+m)，在大文本场景下非常关键；第三，它的设计思路，也就是“利用已经比较过的信息避免重复劳动”，影响了后面大量的字符串算法。

1.2 暴力匹配是怎么做的

在没人教KMP之前，大多数人写字符串匹配都会先写“暴力版”。思路非常直白：把主串的每一个位置都当作一个可能的起点，从那里开始和模式串逐字符比较，一旦发现不同，就把起点往后移动一位，重新比较。

写成C语言差不多是这样：

int bruteSearch(const char *t, const char *p) { int n = strlen(t), m = strlen(p); for (int i = 0; i + m <= n; i++) { int j = 0; while (j < m && t[i + j] == p[j]) { j++; } if (j == m) { return i; } } return -1; }

外层循环决定起点，内层循环做逐位比较。这种写法简单、直观、不容易出错，但性能隐患非常大。假设主串是“aaaaaaaaaaaaaaaaab”，模式串是“aaaab”，当起点在0的时候，前4个字符都相等，到第5个字符才发现不一样，于是起点挪到1，又重复比较前4个字符……每次都做同样的工作，直到最后才找到答案。

这个例子的复杂度一眼就能看出来：主串长度几乎全是重复字符，模式串长度又比较长，最坏情况下要做接近n*m次字符比较。很快慢到没法接受。更残酷的是，这还不是故意构造的极端数据，现实里搜索重复序列、固定内容、模板片段，都可能撞上类似情况。

1.3 暴力浪费的根源到底在哪

暴力法的核心浪费，在于失配以后把已经比较过的信息全部丢掉了。主串的指针要回退，模式串的指针也要从头再来，等于之前读过的那一串字符全都白读。

举个例子，你在一个非常长的文本里查找一个段落关键词，读到了第2000个字符才失配，暴力法会把这个位置前后已经确认过的内容全部作废，转回去从第2个字符再读一遍。这种重复劳动的频率一高，性能就崩了。

KMP的思路一反常识：主串指针永远不回退，失配之后只让模式串指针移动。这听起来像是不可能完成的任务，因为它必须知道“模式串应该跳到哪个位置继续”，而这个跳转信息就是KMP里的核心——next数组。

2. KMP的核心思想：前缀后缀与next数组

2.1 用生活里的直觉理解“记住已有信息”

设想一下，你在一本书里找一句之前见过的话，读到某一页时发现后面接的内容对不上。你不会翻回第一页重新读，你会站在原地思考：刚才看到的这段文字里，最后几个字和我要找的那句话的开头重复了吗？如果重复了，那就从这个重复点后面继续往下找。

KMP干的正是这件事。它之所以让主串指针不回退，是因为在每一轮匹配中，主串里已经有一段字符被确认过“和模式串的前若干字符相同”。失配发生时，这段已确认的字符并没有作废，它的尾部和模式串的头部可能有一部分重叠。只要把模式串向右滑动到让那段重叠的头部对准刚刚扫过的尾部，就可以直接从失配字符接着比较，完全不用把主串指针退回去。

所以KMP要解决的第一个问题，就是“模式串自己的前缀和后缀能有多长的重叠”。这个重叠长度，就是跳过无效比较的依据。

2.2 真前缀与真后缀的定义

为了避免术语劝退，先把两个概念用最简单的话说清楚。

一个字符串的前缀，就是从左往右截出来的若干个连续字符；后缀，就是从右往左截出来的若干个连续字符。注意这里说的都是“真前缀”和“真后缀”，也就是不能取整个字符串自己。比如“ABABC”，它的真前缀有：“A”、“AB”、“ABA”、“ABAB”；它的真后缀有：“C”、“BC”、“ABC”、“BABC”。两边都不包含“ABABC”本身。

如果某个前缀和后缀一模一样，那就叫“公共前后缀”。把长度最长的那一个找出来，长度值就是“最长公共前后缀长度”。例如“ABAB”这个字符串，真前缀里有一个“AB”，真后缀里也有一个“AB”，所以最长公共前后缀长度是2。而“ABABC”里没有长度超过0的公共前后缀，所以这个值是0。

理解到这一步，KMP就已经入门了一半。next数组本质上就是在回答一个简单的问题：模式串从左到右逐位增长时，每一截的最长公共前后缀分别是多少。

2.3 next数组到底存了什么东西

网上关于next数组的代码五花八门，主要原因是对next数组的定义不统一。我在这篇文章里先采用一种最常见的定义：

next[j]表示模式串P从开头到下标j-1这一段的“最长公共前后缀长度”，并且约定next[0] = -1。

为什么要有-1这种奇怪的值？因为next数组不止要存“长度信息”，还要在匹配时作为“失配跳转的下标”来用。当模式串第0个字符就失配时，它已经没有任何前缀可以对齐了，这时候必须让主串指针前进一位，模式串还是从0开始。用-1作为一个特殊标记，恰好方便代码里统一判断。

举个例子，模式串是“ABAB”，那么：

• next[0] = -1，约定值
• next[1]考察的是“A”，最长公共前后缀长度为0
• next[2]考察的是“AB”，最长公共前后缀长度为0
• next[3]考察的是“ABA”，前缀“A”和后缀“A”相同，长度为1

失配跳转时，如果当前比较到了P[j]但字符不相等，就让j = next[j]，然后用新的P[j]继续和主串当前位置比较。也就是说，next数组是一张“失配之后下一步怎么办”的跳转表，它把匹配失败时浪费的比较全部省掉了。

3. 手把手计算next数组：两个实例讲透

3.1 用模式串“ABABCABAB”完整推导

空口讲定义不够直观，我们直接拿一个模式串手工推导一遍。给定P = “ABABCABAB”，长度是9，下标从0到8。

逐步计算：

自己动手算的时候，我推荐一个笨办法：把每一段的真前缀和真后缀先列出来，再找相同项。比如“ABABCABA”，前缀集合包括A、AB、ABA、ABAB、ABABC、ABABCA、ABABCAB，后缀集合包括A、BA、ABA、CABA、BCABA、ABCABA、BABCABA。两边都出现的最长项是“ABA”，长度3，所以next[8]等于3。

这个值在实际匹配中是什么意思？当模式串比较到第8个字符失败时，说明它之前匹配成功了8个字符，也就是“ABABCABA”。这时候模式串已经读过的内容里，尾部3个字符“ABA”和头部3个字符“ABA”完全一致，所以可以让模式串直接跳到下标3，拿P[3]和刚才失配的主串字符重新比较。这样就不会把“ABA”这3个字符再重新匹配一遍。

3.2 为什么网上有两种稍微不同的next定义

很多初学者最大的困惑，就是同一个模式串，在这个教程里next是这么写的，在那个教程里next是那样写的，看代码好像都对，混着用却错得离谱。

两种常见的定义分别是：

第一种，前缀函数式定义：next[j]表示P[0..j-1]的最长公共前后缀长度，next[0] = -1。这也是一部分教材的做法。

第二种，失配跳转式定义：next[j]表示匹配到P[j]失配时，模式串下一步应该跳到的下标。这种定义通常会把上一个定义的next数组整体右移一位，再在最前面补一个-1，或者从0开始编号时做其它调整。

网上有些教程还会把这两种定义混着写，所以你会看到有的地方next[3]=1，有的地方next[3]=0，看得一头雾水。其实算法本身没有变化，变的只是表的“存储格式”。

我个人建议你先固定住上面第一种定义，因为它和“最长公共前后缀”这个概念直接对应，手算的时候不容易出错。等你把第一种定义下的算法彻底搞懂了，再去看第二种写法，会发现只是把下标错位了一下，并不难理解。千万别同时背好几套模板，否则写代码的时候一定会乱。

4. 代码实现：从next到完整的KMP匹配

4.1 求next数组：巧用“模式串匹配自己”

KMP代码里最容易被卡住的地方，就是next数组的生成过程。其实它的原理可以概括成一句话：拿模式串自己和自己做匹配。

通俗地说，我们让两个指针分别跑在模式串的“前缀”和“后缀”上。一个指针记录当前已经匹配到多长的前缀，另一个指针遍历模式串的每一个位置，一旦发现后缀里出现了前缀的影子，就记录下这个重叠长度。

void getNext(const char *p, int *next) { int m = strlen(p); next[0] = -1; int i = 0, j = -1; while (i < m - 1) { if (j == -1 || p[i] == p[j]) { i++; j++; next[i] = j; } else { j = next[j]; } } }

这里i可以理解成“后缀部分的末尾”，j可以理解成“前缀部分的末尾”。初始时j = -1，表示前缀还没有任何字符匹配上。

循环里只有两种情况：

• 当前的p[i]和p[j]相等，说明公共前后缀可以继续延长，于是i和j一起前进，并且记录下next[i] = j。
• 两者不相等，说明这个位置不能继续延长了，j要按已经算好的next数组回退，相当于“用模式串自己的失配信息来指导下一步”。

为什么循环条件是i < m - 1？因为next[m-1]指的是P[0..m-2]的公共前后缀长度，它会在i = m-2那一步被记录；而next[m]在匹配过程中用不到，模式串整体匹配成功就结束了，不需要为“第m个字符失配”准备跳转信息。

4.2 匹配主循环：失配时怎么跳

有了next数组，KMP的主匹配函数就非常简单了。主串指针i始终向前走，模式串指针j按照next数组来回调整。

int kmpSearch(const char *t, const char *p) { int n = strlen(t), m = strlen(p); if (m == 0) { return 0; } int *next = (int *)malloc(sizeof(int) * m); getNext(p, next); int i = 0, j = 0; while (i < n && j < m) { if (j == -1 || t[i] == p[j]) { i++; j++; } else { j = next[j]; } } free(next); if (j == m) { return i - j; } return -1; }

写这段代码的时候有两点要特别注意。

第一，当j变成-1时，说明模式串的前缀彻底对不上了，主串指针必须前进一位，模式串从头开始比较。所以代码里判断了“j == -1”这个条件，它和“字符相等”被放在同一个分支处理，是因为这两种情况都会让i和j同时往前推进。

第二，匹配成功后返回的是i - j，因为循环结束时i已经指向主串中匹配段末尾的下一个位置，减去模式串长度j，就是这段匹配的起始下标。

严格来说，上面这种写法还没做“连续重复字符”的优化，但这不影响正确性，也不影响理解。我建议初学者先把这一步跑通再说优化。

4.3 nextval优化：解决连续重复字符的重复劳动

如果一次失配后，新的P[j]和刚刚失配的P[j_old]完全相同，那么跳到新位置后还是会失配，等于白跳了一次。针对这个问题，可以在生成next时做一层判断：如果当前要填入的next[i]和模式串对应位置的字符相同，就继续往前回溯。

优化后的生成函数长这样：

void getNextVal(const char *p, int *next) { int m = strlen(p); next[0] = -1; int i = 0, j = -1; while (i < m - 1) { if (j == -1 || p[i] == p[j]) { i++; j++; if (p[i] == p[j]) { next[i] = next[j]; } else { next[i] = j; } } else { j = next[j]; } } }

对比一下能发现，逻辑主体没变，只在给next[i]赋值前加了一个判断。这个优化在模式串有大量重复字符时收益很明显，比如模式串是“AAAAA”，遇到失配时原本可能需要连续跳好几步，优化后一步就定位到正确位置。

网上很多代码把这个版本直接叫next数组，实际上它更准确的名字是nextval。奉劝新手不要纠结两个名字，先能把基础版写对，优化版不过是多了个“防止重复比较”的小技巧而已。

5. 完整匹配流程走读：每一步都有据可查

5.1 真实例子：主串“abcabxabcabd”与模式串“abcabd”

光看代码还是不直观，我们完整走一遍匹配过程。主串T = “abcabxabcabd”，模式串P = “abcabd”。

先算P的next数组。P = “abcabd”，长度6：

• next[0] = -1
• 考察“a”，next[1] = 0
• 考察“ab”，next[2] = 0
• 考察“abc”，next[3] = 0
• 考察“abca”，最长公共前后缀是“a”，next[4] = 1
• 考察“abcab”，最长公共前后缀是“ab”，next[5] = 2

所以next = {-1, 0, 0, 0, 1, 2}。

接下来从i=0、j=0开始匹配。

最终j=6，等于模式串长度m，返回i-j=12-6=6，也就是主串下标6。

整个过程里，主串指针i从0增加到12，从来没有回退过。模式串指针j虽然经历了一次次回跳，但它的回跳完全靠next数组完成，不会触发主串重新扫描。这就是KMP带感的地方。

5.2 失配跳转为什么不漏掉可能的匹配

看到这里，不少人的第一反应是：主串指针一直往前走，万一真正的匹配起点被跳过去了怎么办？

答案藏在next数组的性质里。假设我们在i位置失配，说明主串从某个位置到i-1这段，刚好和模式串的P[0..j-1]完全相等。也就是说，主串当前位置前面这一段的后缀，等于模式串这一截的前缀。把模式串向右滑动，让这个相同的前后缀对准，那么模式串开头的那部分字符已经天然和主串匹配好了，完全不需要再比较。

真正被跳过的，是那些已经被证明不可能成为匹配起点的位置。因为模式串要匹配成功，它开头的字符必须和主串某一段完全一致，而主串刚刚从前往后扫过的每段情况都已经记录在案，凡是不可能的地方，模式串要么滑过去，要么被next数组直接规避。

这个“不回溯且不遗漏”的特点，正是KMP区别于暴力法的根本原因。

6. 复杂度分析：KMP快在哪里，慢在何处

6.1 两个循环的均摊分析

KMP的时间复杂度为什么是O(n+m)？要解释清楚，得分别看它的两个阶段。

先看主匹配循环。主串指针i在每次比较后要么前进，要么保持不变；但i只有在“字符匹配成功”或“j为-1”时才会增加。所以整个匹配过程中i最多增加n次，这一点没有争议。

那j不断回跳会不会导致循环次数爆炸？不会。j的每一次回跳，都是因为之前j曾经从某个较小值增加到了当前值。也就是说，j能回跳多少次，取决于j之前一共增加过多少次。j增加一次，往往伴随着i增加一次，所以j回跳的总次数被n限制住。综合下来，主循环的总执行次数是O(n)。

再看生成next数组的过程。它本质上就是模式串自己和自己匹配，模式和主循环一模一样，只是“主串”变成了模式串自身。所以它的总执行次数是O(m)。

合在一起，KMP的时间复杂度是O(n+m)。这个结论在数学上成立，在实际运行中也站得住脚。空间上多了一个长度为m的next数组，所以空间复杂度是O(m)。

6.2 “线性”背后的几个真相

线性复杂度听起来很美好，但有几个细节需要泼一下冷水。

第一，KMP的常数项不算小。每次失配都要读取next数组，再根据结果调整指针，过程中还多了一次额外判断。如果主串很短、模式串很短，KMP未必比暴力法快多少。它真正的优势体现在大规模文本、重复模式或者最坏情况频发的场景里。

第二，随机文本下暴力法往往表现不差。因为大多数情况下，模式串的第一个字符就能让大多数起点立刻失败，暴力法很多时候实际复杂度接近O(n)。所以不存在“任何时候KMP都碾压暴力”的说法。

第三，KMP的空间占用虽然只有O(m)，但在现代缓存友好的算法面前，单次字符访问的顺序性和局部性也可能影响到实际性能。这就是为什么很多成熟的文本工具会选用其它更激进的匹配策略，而不是一律套KMP。

7. 避坑清单与验证方法

7.1 先统一next定义，再写代码

我见过太多人，写代码前不定义清楚next数组的含义，直接照抄网上的模板，结果抄出来的代码在某些用例上正确，换一个模式串就崩。

比如有的模板里next[0]=-1，有的模板里next[0]=0；有的模板里next[i]记录的是“长度”，有的模板里记录的是“跳转位置”。一旦你把两种模板拼在一起，逻辑立刻错乱。

我的建议是：写之前先在注释里写清楚“next[j] = P[0..j-1]的最长公共前后缀长度，next[0]=-1”。然后严格按照这个定义去验证几个模式串，跑通了再继续。

7.2 几个必须测试的边界用例

字符串算法的边界问题特别多，凡是靠肉眼检查代码很难发现。我一般会用下面这组用例做快速验证：

• 模式串为空串：应该返回0，而不是越界访问
• 主串为空串：应该返回-1
• 模式串长度大于主串：直接返回-1
• 模式串和主串完全相同：返回0
• 模式串只有一个字符：检查匹配逻辑是否依赖ne数组越界
• 模式串全是重复字符：比如“aaaaab”和主串“aaaaaaaaaaab”
• 模式串存在大量重叠后缀：比如“ababa”和主串“xxababaxx”

这组用例覆盖了大部分容易出错的场景，跑通了基本没有大问题。

7.3 用对拍方法验证正确性

如果你觉得手推太累，最可靠的方式是对拍。也就是写一个暴力匹配函数，再写一个KMP函数，然后生成大量随机字符串，对比两者返回的起始下标是否完全一致。

哪怕只生成几百组长度为几十的随机串，也能把大多数隐性问题暴露出来。我自己经常用Python写个几十行的小脚本做这件事。核心逻辑就是for循环里随机生成主串和模式串，分别调用两个实现，发现结果不一致就打印出来。

需要注意的是，生成随机串时不要只用普通字母，还应该加入少量重复字符集合，比如只从“aaaaaa”和“bbbbbb”这种字符池里取，这样才能覆盖KMP最容易出错的连续重复场景。

7.4 一个容易忽略的细节：模式串重复字符的nextval

有的同学测试普通模式串时一切正常，一到“ABABABA”这类高重复模式串就出问题，原因往往是把未优化的next和优化版的nextval混用了。

未优化版本的next值，在某些连续重复字符场景下会让j跳好几次。优化版本的nextval直接跳到了更远的位置。两者虽然在最终结果上一致，但产生的跳转序列不同，如果调试时看跳转过程，会觉得逻辑对不上。

我的经验是：学习阶段只用未优化版本，理解清楚以后再换优化版，不要一上来就背着nextval的模板糊里糊涂地抄。

8. 我的学习路线参考

如果让我重新学一遍KMP，我会按下面这个顺序走。

第一步，先用暴力法写一个能跑通的字符串匹配，再构造一个类似“aaaaaaaaab”和“aaaab”的用例，亲眼看看暴力法到底慢在哪。第二步，花一整个下午手推三个模式串的next数组，每个位置都画出前缀后缀集合，不跳步。第三步，自己实现主匹配代码，并对着第5小节的完整例子走一遍流程。第四步，再去看nextval优化，这时候你会发现所谓的优化不过是一层小判断。

最后再分享一个实操技巧：实在记不住代码时，不用硬背模板，只要记住两个原则就够了——next记录的是“已经匹配过的部分里，前缀后缀最长的重叠长度”，主循环里失配后让j = next[j]而不是让i回退。这两句话想通了，代码是能现场写出来的。

KMP不是那种一遍就能彻底吃透的算法，我当年也推错过好几次next数组。但正因为它的设计绕了几个弯，真正理解之后，你会发现字符串匹配背后“用历史信息指导未来跳转”的思路，在算法世界里到处都是它的影子。