企业官网建设流程全解析

1. 从一次暴力匹配的重复劳动说起

字符串匹配这件事，平时看起来没什么技术含量。在文本里找一个词，谁不会呢？但真正处理过大规模文本的人会告诉你，朴素的逐位匹配方案在特定数据下能慢到你怀疑人生。我第一次明显感受到这一点，是在做一次日志分析任务的时候：几万条日志里筛包含特定错误码的行，用最简单的双重循环去搜，数据量一上来速度肉眼可见地往下掉。也是从那时候起，我去翻了翻KMP相关的内容，认真写了一版学习笔记，今天这篇就是把其中最关键的部分整理出来。

KMP全称是Knuth-Morris-Pratt算法，由三位计算机科学家联合提出。它解决的还是那个老问题：在一个主串中查找某个模式串是否出现、出现在哪里。和朴素匹配最大的不同在于，KMP能利用已经匹配成功的部分信息，让主串下标永不回退，模式串的下标也不傻傻地回到头重新来。这个思想听起来简单，但真正落实到位需要一套精巧的前缀函数，也就是大家常说的next数组。

这篇笔记适合两类人看：一类是刚开始学算法、被KMP的跳转规则绕晕的初学者；另一类是工作中要做文本匹配、想从底层原理上理解匹配器行为进而做出性能取舍的开发者。我会把next数组的推导过程、代码实现、常见坑都拆开讲，尽量让每个步骤都有“为什么”的解释，而不是死记公式。标题虽然是“学习纪要”，但这篇记录的其实是我从懵到懂的全过程，里面所有推导和踩坑都是真实跑过的，不是抄书。

1.1 朴素匹配到底把时间浪费在哪了

先看朴素匹配的做法：主串长度为n，模式串长度为m，最坏情况下每次匹配失败都从头开始，总比较次数是O(n*m)。举一个最极端的例子，主串是AAAAAAAAAAAAAAA...，模式串是AAAAB，每尝试一个位置都要比到最后一个字符才发现不匹配，然后整体右移一位再来一遍。这种重复扫描造成的浪费非常直观：上次匹配到一半的信息全部丢弃了。

这种浪费的本质是什么？是文本指针被迫回溯。比如主串第i个字符和模式串第j个字符比较失败后，朴素算法会把主串指针退回到起始位置的下一个位置，模式串指针清零。可实际上，主串从这一轮起始位置到失败位置之间的字符，我们已经全部看过了，里面蕴含了很多“模式串前缀在当前位置能匹配多长”的信息，白白丢掉再重扫一遍，这就是低效的来源。

很多人会问，现代编程语言里的字符串查找函数不是挺快的吗？那是因为底层实现针对常见场景做了大量优化，比如快速跳过不可能命中的位置。但如果你要理解字符串匹配的边界行为，或者要在特定业务场景下做定制匹配，KMP这套“失败时如何优雅后退”的框架依然是最值得理解的基础。

1.2 KMP的核心思想：拿匹配失败当信息，而不是当成本

KMP把匹配失败这件事从“损失”变成了“线索”。它提前对模式串做一次预处理，算出一个next数组。这个数组的含义是：当主串与模式串在第j位失配时，模式串的指针应该回退到哪个位置继续比较。因为主串指针不回退，所以主串只会从0扫到n-1，一共扫描一次；模式串指针虽然有回退，但每次回退都有明确依据，总体代价是O(n+m)。

打个通俗的比方：假设你在读一本书，要找一个固定句子。朴素方案是每找到一个和句子开头相似的字，就从该位置重新逐字对一遍，失败了再往下一个位置试。KMP的思路则是：这句话的一部分已经和书里的内容匹配上了，这部分里存在多少“既是句子前缀又是当前已匹配部分的结尾”的重叠，下一次我只需要从重叠之后的字符开始比对。你只是在失败的那一个点上换了个字接着读，不需要倒回去重读。

这个思路的落地核心就是前缀函数（前缀表）。怎么算、怎么用，决定了KMP的两个版本——经典next数组和优化的nextval数组。下面两节先把经典版本完全讲透。

2. next数组的构造：最长相同前后缀的逐位推导

next数组是KMP的“预计算智能”，它本身不依赖主串，只依赖模式串。我们要预先回答这样一个问题：对于模式串的每一个前缀子串，它最长的、既是前缀又是后缀的子串有多长？这个最长公共前后缀的长度，通常记作π值（pi值），也有很多人直接把它当成next数组用，只是写法和下标起点不同。我这篇采用一种写法，尽量让写代码时容易对齐、不易出错。

2.1 前缀函数的定义：别被“最长相同前后缀”绕晕

先严格定义一下。设模式串P的长度为m，P的一个前缀子串P[0..i]，它的前缀函数值π[i]定义为：该子串中，长度最长且不等于该子串本身的、既是前缀又是后缀的子串的长度。注意这里有个隐含限制：不能是整个子串本身，否则π[i]=i+1，逻辑上就坏了。

举个例子，模式串ABABC，看前缀子串ABAB：

• 它的前缀有：A、AB、ABA
• 它的后缀有：B、AB、BAB
• 同时属于前缀和后缀的，只有AB，长度为2

所以π[3]=2。再看ABA：

• 前缀：A、AB
• 后缀：A、BA
• 共同的是A，长度为1

所以π[2]=1。这个值的含义是：如果我们在主串里已经匹配到了AB（模式串前两位），下一个该比较哪个位置？答案是从长度为2的公共前后缀的下一格开始，也就是模式串下标2对应的A。

2.2 手工推导实例：以“AABAAAB”为例拆开看

这一节我建议你拿纸笔跟着写一遍。模式串取AABAAAB，长度为7，下标从0开始。我们逐个计算π值。

i=0：子串A，没有真前后缀，π[0]=0。

i=1：子串AA，前缀A、后缀A相同，长度为1，π[1]=1。

i=2：子串AAB，前缀A、AA；后缀B、AB，无一相同，π[2]=0。

i=3：子串AABA，枚举前缀和后缀：

• 长度为1：前缀A、后缀A，相同，长度1成立
• 长度为2：前缀AA、后缀BA，不同
• 长度为3：前缀AAB、后缀ABA，不同 保留最长的成立长度，π[3]=1。

i=4：子串AABAA：

• 长度为1：前缀A、后缀A，相同
• 长度为2：前缀AA、后缀AA，相同
• 长度为3：前缀AAB、后缀BAA，不同
• 长度为4：前缀AABA、后缀ABAA，不同 最长相同前后缀长度是2，但注意π[4]并不是直接更新成2的——它对应的下标是2，表示“如果失配，可以跳到模式串下标2继续”也即AABAA的前2个字符AA和最后2个字符AA重叠。π[4]=2。

i=5：子串AABAAA：

• 枚举会得到AA是最长公共前后缀吗？看一下长度为3：前缀AAB、后缀AAA，不同；长度2：前缀AA、后缀AA，相同，于是π[5]=2。

i=6：子串AABAAAB：

• 长度3：前缀AAB、后缀AAB，相同！
• 长度4：前缀AABA、后缀AAAB，不同
• 长度5、6也不用看了 最长公共前后缀长度是3，π[6]=3。

把结果整理成一张表：

这张表手工推完，你对前缀函数的基本含义应该就有体感了。π[i]的数值本身不是“跳转目标”的全部，真正写代码的时候，如何从π值得到回退位置还有细节要处理，下面会讲到。

2.3 双指针递推的代码实现

手工推导能帮你理解定义，但真正写代码时不可能每次重新枚举一遍前缀后缀，那样复杂度又变成O(m²)了。高效构造π数组用的是双指针递推法，核心思路是：每次在已计算出的π[i]的基础上，看新加入的字符P[i]能不能“接续”之前的匹配长度。

def build_pi(pattern): m = len(pattern) pi = [0] * m j = 0 for i in range(1, m): while j > 0 and pattern[i] != pattern[j]: j = pi[j - 1] if pattern[i] == pattern[j]: j += 1 pi[i] = j return pi

这段代码j表示当前已经匹配的前缀长度。i从1开始向右扫描，遇到不匹配就通过pi[j-1]回退j，这个回退过程和主匹配时的回退逻辑完全一致。为什么可以这么写？因为模式串的“已匹配前缀”和“当前考察后缀”本身就是一个正在进行的小规模KMP匹配，P[i]相当于是那个主串的当前字符，P[j]是模式串的当前字符。理解了这个递归关系，KMP的所有代码就统一了：构造π的过程，其实就是模式串自己匹配自己的过程。

这段代码有个细节要注意：j回退的方式用的是pi[j-1]而不是j-1。很多人在这一步卡住，以为j直接减1就行。直接减1会丢失“重叠部分还能部分匹配”的信息，导致漏掉正确的候选位置。回退到pi[j-1]，本质是让j跳到“当前已匹配前缀的最长相同前后缀长度”处继续比较，这样才能保证不遗漏任何潜在匹配点。

3. 主匹配中的跳转逻辑：为什么模式串只前进不后退

算好next数组，接下来是真正在长文本里跑匹配。KMP匹配主串时只有一个循环，主串指针i从头走到尾，模式串指针j根据情况前进或回退。i永远不回退，这是KMP性能优越性的直接来源。

3.1 主串下标不回退的实际含义

我见过不少人对“主串下标不回退”有误解，以为KMP是完全线性扫描、连一次多余的字符比较都没有。不是的。主串指针i确实不回头，但同一段字符仍然可能被比较多次，因为模式串指针j回退后，会再次用当前主串字符和新的模式串字符做比较。整体复杂度仍然是O(n+m)级别：i走n步，j每次回退都会减少，j总体增长不超过n+m的量级。

看看一个完整的匹配函数实现，接上一节的build_pi：

def kmp_search(text, pattern): if not pattern: return 0 pi = build_pi(pattern) j = 0 for i in range(len(text)): while j > 0 and text[i] != pattern[j]: j = pi[j - 1] if text[i] == pattern[j]: j += 1 if j == len(pattern): return i - j + 1 return -1

如果你把build_pi和kmp_search并排放在一起，会发现它们长得极其相似，都是“while回退 + 相等则前进”的骨架。这印证了前面说的观点：KMP的精髓在于用一个统一规则处理失配，无论是预处理阶段还是主匹配阶段。一旦理解了这个统一规则，剩下的都是体力活。

3.2 跳转到底怎么选：k = next[k-1] 还是 next[k]

不同资料里next数组的写法有差异，有的叫next、有的叫fail、有的叫prefix，有的下标从0开始，有的从1开始，有的把next整体右移一位。这些差异会让初学者非常崩溃：明明看懂了A文章的推导，再看B文章的代码就对不上了。我的建议是，认准一种写法并用到底，这篇笔记里统一用的是“π数组”风格：π[i]表示模式串前i+1个字符组成子串的最长公共前后缀长度。失配时，j回退到π[j-1]。

举一个简单例子验证跳转过程。模式串是ABABC，π数组是[0,0,1,2,0]，在回退时：

• 匹配到下标3失配，此时j=3，已匹配的是ABA，π[2]=1，说明已匹配部分的首尾有1个字符重叠，所以j回退到1，重比P[1]。
• 如果回退后仍不匹配，继续回退：此时j=1，π[0]=0，退到0，从头开始。

这里为什么要一级一级退，而不是直接退到0？看一个例子：模式串AAAB，主串AAACAAAB，匹配到主串第3个字符C时，模式串已经匹配了AAA，失配。这时π[2]=2，回退到j=2，再看主串当前字符C和模式串P[2]=A是否相等，不相等，再回退π[1]=1，还是不相等，再回退到0。如果用直接清零的方式，解法没错，但多一次比较也没多太多开销；可如果模式串是AAAAAAAAAB这种极端串，直接清零就会退化成明显更慢的匹配。这就是逐级回退的价值：利用前缀重叠信息，尽可能保留已匹配的进度。

4. next数组能再优化吗：nextval解决连续重复字符问题

经典next数组理论上已经把复杂度压到了线性，但仔细分析仍能发现它在某些模式串上做了“无用比较”。针对这类情况的优化就是nextval，很多人也叫它“KMP的改进版”。我第一次看到这个优化时觉得多此一举，直到跑了一个全是重复字符的测试用例才发现差距确实存在。

4.1 一个暴露效率问题的例子

考虑模式串AAAA，它的π数组是[0,1,2,3]。如果主串是AAAAB，匹配过程会遇到什么情况？主串前三个字符AAA顺利匹配，模式串j=3，第4个字符模式串是A，主串第4个字符是A，也匹配，j=4等于模式串长度，找到匹配。这个倒没什么问题。

换个场景：主串是AAAB，模式串是AAAA。匹配到j=3、i=3时，P[3]=A和T[3]=B失配。此时j=3，π[2]=2，回退到j=2，比较P[2]=A和T[3]=B，失配；再回退π[1]=1，比较P[1]=A和T[3]=B，失配；再回退π[0]=0，比较P[0]=A和T[3]=B，失配。总共额外做了3次必败的比较。

问题就出在回退后的字符和失配前的字符一模一样：既然P[3]=A和主串字符B不匹配，那回退到P[2]=A、P[1]=A、P[0]=A再去比较同一个主串字符，结果必然还是不匹配。这几次回退就是纯浪费。

4.2 nextval的修正规则

针对上述问题，nextval的思路是：如果回退后的字符和回退前的字符相同，那就继续回退，直接跳到第一个与失配字符不同的位置。构造nextval有两种常见办法：一是在原有π数组基础上再扫一遍做修正；二是用递推方式直接生成修正后的数组。

修正规则可以写成：

def build_nextval(pattern): m = len(pattern) pi = [0] * m j = 0 for i in range(1, m): while j > 0 and pattern[i] != pattern[j]: j = pi[j - 1] if pattern[i] == pattern[j]: j += 1 pi[i] = j # second pass: apply correction for i in range(1, m): if pattern[i] == pattern[pi[i]]: pi[i] = pi[pi[i]] return pi

第二趟扫描中，pi[i]现在是回退目标。如果模式串在位置i的字符，和在回退目标位置pi[i]的字符相同，说明回退过去后还会做一次无效比较，所以直接把pi[i]覆盖成pi[pi[i]]，即跳到那个位置对应的回退目标。这样一层层跳下去，最终得到的是“跳过所有相同字符”的修正结果。甚至主匹配函数一行都不用改，因为失配时执行j = pi[j-1]，使用的是已经修正过的pi值。

拿模式串AAAA举例，原本pi是[0,1,2,3]，修正后变成[0,0,0,0]。主匹配时j=3失配，直接回退到0，省掉了中间3次无意义比较。这一优化在纯重复模式串上的收益非常明显，而在普通随机字符串上影响不大，所以很多现成库函数里不一定实现，但理解它的存在能帮你彻底搞懂KMP系列。

5. KMP实战中的高频应用与扩展

很多初学者以为KMP只能用来做“找字符串”，其实它只是字符串匹配的基础模块，广泛应用于各种需要子串定位、模式扫描、文本对齐的场景。这里结合我的实际使用经验，列几个最常遇到的场景。

5.1 文本过滤：敏感词匹配场景

内容平台做敏感词过滤时，通常会维护一个敏感词表，把用户输入的文本和词表做匹配。简单做法是逐个词去KMP搜索文本，复杂度是O(K*(n+m))，K是词表大小，n是文本长度，m是词平均长度。对中型词表来说这个量级勉强够用，但它有一个隐含问题：每匹配一个词就要把主串完整扫一遍，如果文本和词表都很大，CPU消耗很可观。

基于KMP的改进思路是：把所有敏感词用前缀树（Trie）组织，然后在扫描文本时做“多模式匹配”，比如Aho-Corasick算法，它的核心构造思路大量借鉴了KMP的回退思想。KMP是单模式匹配的基础，AC自动机可以理解为把KMP的前缀函数推广到了树上。如果你要把词表规模做得很大，AC自动机几乎是绕不开的，而KMP正是理解它的阶梯。

5.2 KMP与标准库查找、正则的取舍

实际开发中，别一上来就手写KMP，要结合场景选工具。标准库的str.find、indexOf在大多数场景下已经很快，底层例如memchr结合快速跳跃等优化，对短模式串的性能非常好。KMP更适合哪些场景？一是模式串比较长且包含较长的重复前后缀；二是主串很大，需要一次性扫描并统计多次出现；三是需要在模式串匹配过程中定制额外逻辑，比如找到所有重叠匹配位点。

正则表达式功能远超KMP，但代价是编译正则的开销和回溯风险。KMP的优势在于行为可预期、最坏复杂度有保证。我做日志扫描时，很多场景只用KMP做简单的行内模式定位，比正则更稳、更快，就是因为它不会回溯爆炸。

5.3 KMP的变体扩展

除了前面讲的KMP与nextval，还有一些变体在实际问题中很有用：

• 部分匹配表（Partial Match Table）：很多教材把π数组称为PMT，本质相同，只是使用方式略有不同。
• 字符串的周期性质：KMP的π数组蕴含了字符串的最小周期信息。当m - π[m-1]能整除m时，这个值就是字符串的最小循环节长度。经典判断循环字符串的题目基本都是靠这个性质。
• 扩展KMP（Z算法）：计算主串每个位置与模式串的最长公共前缀长度，生成Z数组，复杂度同样是线性。解决一类需要“每个后缀匹配情况”的问题很有用。
• 在线匹配：如果主串是流式读入，KMP天然支持，因为主串指针不像其它算法那样需要回退，你可以在读入时逐字符喂给匹配器。

6. 学习KMP最常见的三个卡点与我的排查心得

如果说前面几节是从原理到实现的正文，那这一节算是实打实的“避坑笔记”。我自己在啃KMP时踩过的坑、也帮别人排查过的问题，集中在这几类上。

6.1 “明明next数组对，但匹配结果不对”大概率错在哪

遇到这种情况，先别怀疑主匹配函数，几乎九成都是边界条件写岔了。常见错误有这样几个：

• 下标错位：把π数组当成“回退到的下标”直接使用。要注意π[i]的含义是“前i+1个字符组成的子串的最长公共前后缀长度”，失配时j回退到π[j-1]，不是π[j]。
• 漏处理j=0的情况：主匹配循环里，如果j已经是0，失配时就不应该再回退，直接继续主串扫描即可，否则会陷入死循环。
• 模式串为空：很多实现没做“空模式串”保护，一跑就崩。真实项目里一定有人会传空字符串进来，防御性编程要做在前面。
• 只返回第一个匹配位置：如果要找所有匹配，找到一次后不能直接结束，要把j回退到π[j-1]继续扫描，同时注意记录位置时不要漏掉重叠匹配。

我建议把主匹配单独封装成一个函数，输出一个“所有匹配起始位置”的列表，方便测试和复用。平台代码里直接打印start索引会直观很多。

6.2 如何用日志+手工跑一遍来定位问题

如果逻辑推理半天找不出bug，就用最笨但最可靠的办法：小规模手工模拟。选一个短主串、一个短模式串，把π数组打印出来，再逐步打印主匹配过程中每次i、j的变化。对照日志一行一行地核对，看到底哪一步的j回退值和你预期不一致。

我自己调试KMP时常用的一种“穷举验证法”：写一个小脚本，对长度为1到6的所有二进制字符串组合，把KMP的匹配结果和朴素匹配的结果做对比，发现不一样就立刻打印出错案例。这种随机/穷举对拍的方式比任何调试器都好用，几分钟就能把边界情况全扫一遍。尤其是在写nextval或Z算法这种容易下标越界的代码时，暴力对拍几乎是必修课。

6.3 我的个人学习建议

最后说点学习方法上的个人体会。KMP的难点不在代码本身，而在于“为什么失效时回退到那个位置”。我的建议是不要直接背代码，而是做三件事：第一，把前缀函数的定义用自然语言在自己心里重述一遍，确保“最长相同前后缀”这个概念的边界条件都清楚；第二，手工跑至少两个例子，一个普通模式串、一个重复字符模式串，把π数组和主匹配的每一步都写出来；第三，尝试不看任何参考代码写一遍实现，卡住了再对照，往往能发现自己卡住的点是对哪个概念理解不到位。

还有一个很小的心得：不要把“学习KMP”和“使用KMP”混在一起。急着做项目时，直接调标准库函数就行，没必要手写；想搞懂原理时，就从朴素匹配开始逐步推导。先理解再优化，不要在不理解的情况下抄一堆“优化技巧”，那样真到排查问题时会更懵。KMP这套东西真正吃透之后，你再去看AC自动机、后缀数组这类进阶算法，会觉得很多地方似曾相识，因为它们处理失配的核心思路是同源的。