企业官网建设流程全解析

我第一次看KMP算法的时候，感觉像在玩智力游戏：明明一个双层循环就能做字符串匹配，为什么要先折腾出一个next数组，然后匹配的时候还一会儿往前走一会儿往后退？后来自己在项目里处理大文本匹配，才真正体会到朴素匹配的重复回溯有多浪费，也才理解KMP这个1960年代的老算法为什么到今天依然活跃在面试题和工程库里。

这篇笔记是我学习KMP的完整过程复盘，核心围绕三件事：KMP到底优化了什么、next数组（有的叫前缀函数，有的叫部分匹配表）是怎么算的、算完之后匹配阶段怎么用。代码以C++为主，但思路跟语言无关。如果你正卡在“KMP算法next计算方法”这个环节，或者看完一堆教程依然觉得next数组神出鬼没，这篇应该能帮你把链条彻底捋顺。

1. 朴素匹配的重复劳动：KMP到底在优化什么

1.1 朴素匹配的基本流程

最直接的字符串匹配写法，就是拿模式串从主串的每一个位置开始比。用代码表示大概是：

int naiveMatch(const string& text, const string& pattern) { int n = (int)text.size(); int m = (int)pattern.size(); for (int i = 0; i + m <= n; ++i) { int j = 0; while (j < m && text[i + j] == pattern[j]) ++j; if (j == m) return i; } return -1; }

逻辑很好懂：外层循环确定主串的起始位置i，内层循环从i开始逐个比较。一旦中间某个字符不等，就把起始位置右移一位，重新从头比较。对长度n的主串和长度m的模式串，最坏情况的比较次数是O(n*m)。比如T="AAAAAAAAAAAAAAAAAB"（15个A加一个B），P="AAAAB"（4个A加一个B），每一次都要在前面4个字符全部相等后才在最后一个字符处失败，然后只向右挪一格，几乎浪费掉之前所有的比较结果——这就是最典型的退化场景。

1.2 浪费的到底是什么

用一个具体例子感受一下重复劳动。文本T="ABABABCABABABD"，模式串P="ABABABD"。

• 尝试起点i=0：比较6个字符都相等（T[0..5]="ABABAB"），第7个字符T[6]='C'和P[6]='D'不等，失败。
• 尝试起点i=1：第一个字符T[1]='B'就和P[0]='A'不等，直接失败。
• 尝试起点i=2：T[2]='A'、T[3]='B'、T[4]='A'、T[5]='B'四个字符相等，T[6]='C'和P[4]='A'不等，失败。
• 尝试起点i=3：T[3]='B'和P[0]='A'不等，直接失败。

看出问题了吗？i=0和i=2的两次尝试里，模式串的"ABAB"前缀被反复比较了。更关键的是，i=0那次我们已经知道主串的"ABABAB"和模式串"ABABAB"是相等的，这个信息在失配那一刻就被丢弃了。

KMP的思路是：把已经确认匹配的部分留着，利用它来推断模式串下一次该从哪个位置开始比。具体来说，当匹配到第j个字符失败时，前面j个字符已经全部等于主串中对应位置的字符。如果模式串的前缀里有某个子串也等于已匹配文本的后缀，那就可以把这个前缀直接滑到刚才的后缀位置上，避免从模式串开头重新比。

这个“已匹配部分最长相等前后缀”的长度，就是next数组要存的东西。这也是整个算法的灵魂。

2. next数组的本质：最长相等前后缀为什么能决定跳多远

2.1 前缀、后缀与最长相等前后缀

先定义清楚三件事：

• 前缀：字符串中不包含最后一个字符的任意连续头部子串。
• 后缀：字符串中不包含第一个字符的任意连续尾部子串。
• 一个串的最长相等前后缀，就是前缀集合和后缀集合里完全相同的子串中最长的那一个。注意通常不考虑整个串自身作为它的前后缀，否则任何串的最长相等前后缀都是它自己，问题就没意义了。

表里"ABABA"的前缀集合里有"A"、"AB"、"ABA"、"ABAB"，后缀集合里有"A"、"BA"、"ABA"、"BABA"，交集是{"A", "ABA"}，最长的是"ABA"，长度3。

2.2 前缀函数pi到底是什么

记模式串P，定义pi[i]为子串P[0..i]的最长相等前后缀长度。比如P="ABABAC"的时候：

• pi[0] = 0（"A"）
• pi[1] = 0（"AB"）
• pi[2] = 1（"ABA"）
• pi[3] = 2（"ABAB"）
• pi[4] = 3（"ABABA"）
• pi[5] = 0（"ABABAC"）

所以pi数组 = [0, 0, 1, 2, 3, 0]。

注意pi的定义是“对P[0..i]这个前缀求最长相等前后缀”，而不是只看P[0..i]整体。它是从模式串的开头一路往后，对每个前缀都算一遍。这个数组在很多资料里被称为前缀函数，它是KMP所有版本的基石。

2.3 两种next坐标系：很多教程混乱的根源

网上讲KMP的next数组时，不同文章用的坐标系经常不一样，这是初学者最容易懵的地方。常见的有两种。

第一种是“长度版”，也就是上面这个pi：pi[i]表示P[0..i]的最长相等前后缀长度，从0开始。

第二种是“跳转版”：next[i]表示匹配到P[i]失败时，模式串指针j应该回退到的下标。转换关系是：

next[0] = -1 next[i] = pi[i-1] (i >= 1)

为什么next[0]=-1？因为当模式串第一个字符就和主串当前字符不匹配时，说明主串这个位置没有任何继续匹配的可能，主串指针需要前进，模式串回到开头。用-1作为一个特殊标记，配合匹配循环里++j的操作，就能实现“主串前进且j归零”的效果。

比如P="ABABAC"：

pi = [0, 0, 1, 2, 3, 0] next = [-1, 0, 0, 1, 2, 3]

这两个数组在数学上完全等价，只是表述角度不同。网上很多代码是把两种写法混在一起的，看的时候一定要先确认作者用的是哪一种，否则对照着看会越看越乱。我下面先重点讲长度版的构造原理，再讲如何转成跳转版：长度版更直观，适合理解；跳转版更接近很多经典代码的写法，适合实战。

3. next数组的递推计算：手算推演与代码实现

3.1 手算一个字符串的pi数组

理论说了半天，不如动手算一遍。以P="ABABAC"为例，一步步推pi。算法是这样的：pi[i]可以通过pi[i-1]递推出来。假设已经知道pi[i-1]=j，意思是P[0..i-1]的最长相等前后缀长度是j。现在要看P[i]能否把这个匹配结果继续扩展：如果P[i]==P[j]，说明在原来的前后缀基础上，末尾和开头各多了一个相同字符，所以pi[i]=j+1。如果P[i]!=P[j]，就要退而求其次，观察长度更短的相等前后缀——也就是P[0..j-1]的最长相等前后缀长度pi[j-1]，然后把j更新成pi[j-1]，再比较P[i]和P[j]，如此反复。

最典型的是i=5这一行。P[5]='C'，初始j=pi[4]=3，P[5]='C'和P[3]='B'比较不相等；然后j变成pi[2]=1，再比较P[5]='C'和P[1]='B'，还是不等；j再变成pi[0]=0，比较P[5]='C'和P[0]='A'，仍然不等，最终pi[5]=0。这个“不相等就回退到更短的相等前后缀”的循环，就是KMP计算里最核心的动作，理解了它，构建代码就是水到渠成的事。

3.2 前缀函数的标准C++实现

把上面的手算过程翻译成代码：

vector<int> piFunction(const string& s) { int n = (int)s.size(); vector<int> pi(n, 0); for (int i = 1; i < n; ++i) { int j = pi[i - 1]; while (j > 0 && s[i] != s[j]) { j = pi[j - 1]; } if (s[i] == s[j]) { ++j; } pi[i] = j; } return pi; }

几个细节说明。while的终止条件包含j>0，因为j=0时已经退无可退，这时候如果s[i]!=s[0]，说明当前位置没有任何相等前后缀，pi[i]=0；如果s[i]==s[0]，则pi[i]=1。这一小段代码的时间复杂度是O(n)，虽然while循环看起来可能反复执行，但j的增加次数总共不超过n，每次回退都会让j变小，所以总回退次数也不超过n，这是递推过程仍然线性的关键。

3.3 经典跳转式next的两种实现方式

理解了pi数组，跳转式next就简单了。最简单的方式是直接用转换关系生成：

vector<int> buildNextFromPi(const string& p) { vector<int> pi = piFunction(p); int m = (int)p.size(); vector<int> next(m); next[0] = -1; for (int i = 1; i < m; ++i) { next[i] = pi[i - 1]; } return next; }

但这样要多算一遍pi，还要手动转换。很多资料里会出现一种更紧凑的写法，直接用两个指针边算边存，也是很多面试代码里能见到的风格：

vector<int> buildNext(const string& p) { int m = (int)p.size(); vector<int> next(m); 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]; } } return next; }

这段代码第一次看会觉得像天书，但理解了之后会发现它和pi数组版本是同一个东西。j表示“已经匹配的前缀长度”，j==-1表示回到了起点，p[i]==p[j]表示匹配可以继续延长，于是i和j一起前进，并记下next[i]=j。失配时j=next[j]，就是回退到更短的相等前后缀。我自己的建议是：如果为了写业务代码或考试，直接用pi版最不容易出错，逻辑一条线，没有那么多边界分支；如果为了看别人代码或应付手写，两种都要能秒切换。

4. 匹配主流程：拿着next数组逐位推进

4.1 匹配阶段的代码

构建next数组只是准备工作，真正干活的匹配阶段反而简单。核心代码用pi版本写：

vector<int> kmpSearch(const string& text, const string& pattern) { int n = (int)text.size(); int m = (int)pattern.size(); if (m == 0) return {}; vector<int> pi = piFunction(pattern); vector<int> positions; int j = 0; for (int i = 0; i < n; ++i) { while (j > 0 && text[i] != pattern[j]) { j = pi[j - 1]; } if (text[i] == pattern[j]) { ++j; } if (j == m) { positions.push_back(i - m + 1); j = pi[j - 1]; } } return positions; }

匹配逻辑和构建pi很像，本质上是同一个模式串在和文本“同步”地比较。i永远只前进不回退，j表示当前已经匹配了多少个字符。失配的时候，j回退到pi[j-1]，这个值是“已经匹配的那部分的最长相等前后缀长度”，直接从那个长度继续比较，不再从头开始。这段代码支持找出所有匹配位置，不只是第一个。如果只想找第一个，把push_back那行改成return i - m + 1;即可。

4.2 完整例子：文本"ABABABCABABABD"里找"ABABABD"

先算模式串的pi。P="ABABABD"，逐位推导：

• pi[0] = 0
• i=1：P[1]='B'不等于P[0]='A'，pi[1]=0
• i=2：P[2]='A'等于P[0]，j=1，pi[2]=1
• i=3：P[3]='B'等于P[1]，j=2，pi[3]=2
• i=4：P[4]='A'等于P[2]，j=3，pi[4]=3
• i=5：P[5]='B'等于P[3]，j=4，pi[5]=4
• i=6：P[6]='D'，先与P[4]='A'比较不等，回退j=pi[3]=2，再与P[2]='A'比较不等，回退j=pi[1]=0，再与P[0]='A'比较不等，pi[6]=0

所以pi = [0, 0, 1, 2, 3, 4, 0]。

实际匹配过程完整步进：

• i=0，j=0：T[0]='A'与P[0]='A'相等，j=1。
• i=1，j=1：T[1]='B'与P[1]='B'相等，j=2。
• i=2，j=2：T[2]='A'与P[2]='A'相等，j=3。
• i=3，j=3：T[3]='B'与P[3]='B'相等，j=4。
• i=4，j=4：T[4]='A'与P[4]='A'相等，j=5。
• i=5，j=5：T[5]='B'与P[5]='B'相等，j=6。
• i=6，j=6：T[6]='C'与P[6]='D'不等，进入while循环。第一次回退j=pi[5]=4，T[6]='C'与P[4]='A'不等；第二次j=pi[3]=2，T[6]='C'与P[2]='A'不等；第三次j=pi[1]=0，T[6]='C'与P[0]='A'不等，循环结束。j保持0。
• i=7，j=0：T[7]='A'与P[0]='A'相等，j=1。
• i=8，j=1：T[8]='B'与P[1]='B'相等，j=2。
• i=9到i=12：继续依次匹配"A"、"B"、"A"、"B"，j一路从2涨到6。
• i=13，j=6：T[13]='D'与P[6]='D'相等，j=7。此时j==m，找到匹配，起始位置是13-7+1=7。然后j=pi[6]=0。

注意i=7开始的匹配过程中j一路增长，没有一次回退。整个匹配过程中i从0走到13只前进了一次，这就是KMP的“文本指针不回头”。失配时看起来j在回退好几次，但它的总回退次数受到匹配成功次数的限制，总体还是O(n)。

4.3 把pi版转换成跳转版匹配

如果你手里的next是跳转式（-1开头），匹配循环长这样：

int j = 0; for (int i = 0; i < n; ++i) { while (j >= 0 && text[i] != pattern[j]) { j = next[j]; } ++j; if (j == m) { // 找到匹配，起始位置 i - m + 1 j = next[j]; } }

因为next[0]=-1，while循环可以在j=-1时退出，然后++j让j变成0。这个写法非常紧凑，但存在一个隐蔽的问题：++j之后j可能等于m，如果此时循环继续且没有先处理匹配成功的情况，下一次while里pattern[j]会对下标m越界。所以用跳转式写匹配代码时，一定要保证j==m的分支先重置j，再进入后续循环。两种写法没有优劣，只是风格差异，但边界处理都要想清楚。

5. 复杂度、边界情况与踩坑记录

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

KMP最常被人念叨的就是线性复杂度，但初学的时候很难直观感觉到。可以从两个阶段分别证明。

构建pi，O(m)。外层循环i从1跑到m-1，j的增加次数不超过m，while回退时每次至少减1，而j减少的总次数不可能超过之前增加的次数，所以整个循环体执行次数O(m)。

匹配阶段，O(n)。i从0跑到n-1，j增加的总次数不超过n，同理，while回退的总次数不超过j增加的总次数，也就是O(n)。加起来就是O(n+m)，空间上只需要存模式串长度的数组，O(m)。

对比朴素匹配的O(n*m)，在模式串和文本都很长且重复字符较多时差距非常明显。我实际测试过一个场景：500万字符的文本里查找一个20字符的模式串，KMP只需要几十毫秒级别（主要开销其实在字符串扫描本身），朴素匹配在重复密度高的数据里可能跑出几十倍的差距。

5.2 必须处理的边界情况

以下几类情况我在写KMP时都踩过：

• 模式串为空。m==0时pi数组为空，pi[j-1]一访问就崩，匹配函数入口要直接返回空结果。很多教程根本不提这个。
• 主串比模式串短。代码里没有显式判断，但for循环i<n，j永远达不到m，自然不会有匹配结果，这种场景可以不加特判。
• 全相同字符的模式串。比如P="AAAA"，pi=[0,1,2,3]。匹配阶段失配时，j会沿着pi链一路回退到0，看起来退了很多次，但每次回退都有意义，而且总次数仍然线性。优化版nextval可以让这种情况下j一步到-1，后面会讲。
• 模式串匹配成功后继续查找。这是最容易写错的地方。匹配成功后j应该重置为pi[j-1]，而不是0。重置为pi[j-1]是为了让模式串的重叠部分参与后续匹配。比如P="ABAB"，文本"ABABAB"里有两次匹配，位置0和2，如果匹配成功后j归零，第二次匹配就丢了；重置为pi[3]=2，第二次就能正常找到。

5.3 C++实现里的语言级细节

• 下标类型：计算pi时s[j]的j可能变成0，但如果用size_t，j - 1在j=0时会变成巨大正数，然后访问越界。所以涉及下标运算的地方一律用int，或者显式(int)s.size()。
• pi[j - 1]的访问前提是j>0，while条件里已经保证了这一点，不要为了省一行把while改成do-while。
• 匹配成功分支里pattern[j]的访问前提是j<m。我习惯在j==m分支里先重置j再进入下一次循环，这样就锁死了while里j的取值范围。

以"ABABABD"为例，三个版本对照：

6. 进阶：next数组优化与循环节应用

6.1 优化版nextval

普通的next数组在遇到海量重复字符时还不够聪明。比如P="AAAA"，失配在P[3]时，next[3]=2，跳到P[2]继续比较，可P[2]也是'A'，而当前字符已经因为不等于'A'才失配的，跳到P[2]也必然失败；再跳next[2]=1，还是必然失败。这种重复的失败判断完全可以跳过。

优化思路一句话：如果回退后的字符和失配字符相同，就继续回退到next[next[...]]，直到某个位置候选字符不同，或者退回起点。实现就是经典的nextval：

vector<int> buildNextVal(const string& p) { int m = (int)p.size(); vector<int> next(m); 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] = j; } else { next[i] = next[j]; } } else { j = next[j]; } } return next; }

用P="AAAA"验证：nextval=[-1,-1,-1,-1]，一步到位。用P="ABABAC"验证，失配于P[4]='A'时，next[4]=2但P[2]='A'相同，于是借用到next[2]=0，也符合预期。实测在字符集很小、重复度高的数据上，优化版可以让总比较次数更接近理论下限。

6.2 用前缀函数检测循环节

KMP的前缀函数不止能用来字符串匹配，它还能判断一个字符串是否由某个短串重复构成。有个很妙的性质：对一个长度为n的字符串，如果存在完整的循环节，最小循环节长度是n - pi[n-1]，而且必须满足n % (n - pi[n-1]) == 0。

比如"abcabcabcabc"，n=12，pi[11]=9，n-pi[11]=3，12%3==0，因此周期是3，字符串是"abc"重复4次。为什么是n-pi[n-1]？因为pi[n-1]是“最长相等前后缀”，把字符串最后一个字符拿掉后，最长的重复部分把字符串“压”成了可以错位对齐的两份，错位的距离就是周期长度。这是KMP一个非常实用的副产品，LeetCode的459题就是直接考察这个。

但注意，n%(n-pi[n-1])==0这个条件不能省。字符串"abcabcab"的n=8，pi[7]=5，n-pi=3，8%3!=0，虽然看起来像是"abc"重复了两次半，但它并不存在完整循环节，强行取3会算出错误结论。实际项目中判断循环节，两个条件必须一起用。

int minCycleLength(const string& s) { int n = (int)s.size(); if (n == 0) return 0; vector<int> pi = piFunction(s); int cycle = n - pi[n - 1]; if (n % cycle == 0) return cycle; return n; // 无完整循环节 }

6.3 常见应用场景补充

KMP本身在工程里的出场率其实没有教科书里那么高，因为像C++标准库的string::find、Java的indexOf这类内置函数多用BM系列算法或者SIMD优化，模式串短时不一定比KMP慢。但前缀函数和next思想在以下几个场景里是真有用的：

• 需要返回所有匹配位置的场景。比如基因序列比对、日志关键模式统计，用KMP一次扫描拿到全部起点，而不是反复find。
• 在线或流式匹配。如果文本是流式输入，没法先读完整再匹配，可以用next数组做状态转移，边读入边推进，字符来一个处理一个。
• 字符串的周期性和压缩。检测重复子串、生成最小重复单元，用前缀函数一行逻辑就能拿到。
• 多模式串匹配的入门基础。像AC自动机这种进阶算法，核心就是KMP的失配指针思想从单模式扩展到多模式，理解KMP的next再去看AC自动机会顺畅很多。

最后说点自己的学习体会。我第一次学KMP时也是硬背buildNext那段双指针代码，结果过了两个星期再写就卡住了，因为根本没搞懂那里面i和j到底是什么含义。后来我换了个方法：先理解pi数组的定义，再手算两个字符串的pi数组，最后在纸上把匹配过程模拟一遍，包括那个“失配后j连续回退三次”的细节。做完这些之后，再回去看buildNext的代码，几乎不需要记忆就能自然写出来。

如果你正在学KMP，我建议你也这样走一遍：拿出一张纸，算"ABABAC"的pi，然后再算一个全相同字符的"AAAA"的pi，对比两种情况下回退的区别。把这两组数算熟，KMP就算真正入门了。至于nextval优化、循环节检测这些，都是在这个基础上一句话点透的事情。别看KMP的代码短，它背后那个“利用已匹配信息避免重复劳动”的思想，才是真正值钱的东西。