KMP算法字符串算法圈里绕不开的硬骨头。学的时候容易误以为把next数组的计算模板背下来就万事大吉可真正需要自己实现匹配、排查越界、处理重叠匹配的时候才会发现里面其实藏着不少细节。这篇文章我想从朴素匹配为什么慢讲起把KMP算法的核心思想、next数组计算方法、C实现以及实际工程里的坑完整梳理一遍适合正在准备面试、刷算法题或者在日志分析、文本搜索、词法匹配场景里想自己实现高效匹配的开发者参考。很多人问过我同一个问题KMP是不是已经被各种封装好的字符串匹配库取代了我的看法是封装好的函数确实能解决大部分需求但KMP带来的是一种很底层的思路——如何复用已经扫描过的字符串信息。这个思路在数据流匹配、多模式匹配、甚至某些存储系统的块定位里都能看到影子。把这套东西吃透比单纯背一个模板有价值得多。1. 先搞明白朴素匹配到底慢在哪1.1 从一个最常规的匹配任务说起字符串匹配的任务其实很朴素给定一个文本串text长度为n再给定一个模式串pattern长度为m找出pattern在text中出现的所有起始位置。比如text是ABABDABACDABABCABABpattern是ABABCABAB我们要在text里找到pattern第一次出现或者所有出现的位置。这个任务看起来再简单不过最直觉的写法就是双重循环外层遍历文本的每一个可能的起始位置内层挨个对比字符。一下就能想到的暴力做法实际写出来也很短但它有一个致命问题——在匹配失败之后它会把已经扫描过的文本信息全部丢掉然后文本指针只前进一位模式串指针归零重新开始一场几乎一模一样的比较。在很多场景下这种重复劳动是完全可以避免的。尤其是当模式串比较长、文本串比较长或者两者的自相似性很高的时候暴力的浪费会变得非常明显。1.2 朴素匹配的代码和它浪费掉的比较拿C写一个最基础的暴力匹配很多人第一版是这样的int bruteForce(const string text, const string pattern) { int n text.size(), m pattern.size(); for (int i 0; i n - m; i) { int j 0; while (j m text[i j] pattern[j]) j; if (j m) return i; } return -1; }这段代码的复杂度是O(n*m)。为什么因为外层i每移动一次内层j就可能从头开始比较。想象一个极端例子text是A A A A ... A A Bpattern是A A A A ... A A B前面的字符几乎全部相同如果最后差一个字符那每一轮外层循环都要把前面几百上千个字符重新比较一遍。这种最坏情况在真实数据里并不罕见比如日志文件里大量重复的行、基因序列里的重复片段、代码文件里的缩进和空格。从信息论的角度看朴素匹配最大的问题不是它做了比较而是它在失配后没有保留“已经匹配了多少”这件事。前面明明已经确认text里某一段和pattern的前缀完全相同这个结论在下一轮却被直接抛弃了。KMP算法的核心贡献就是把这份信息留下来继续用。1.3 朴素的优化方向能不能不回头如果让你来设计这个优化你会怎么做我的第一反应是既然已经匹配过的部分主串指针最好不要往回退那能不能只调整模式串的位置让它移动到另一个可能继续匹配的地方这正是KMP做的事。它的基本想法是失配时不把模式串简单右移一位而是根据模式串自身的结构直接跳到某个更靠后的位置。这个“跳”不是凭空来的它依赖于模式串自身前缀和后缀的重叠关系。接下来我们就顺着这个思路拆解。2. 核心思想把失配变成一次“安全跳转”2.1 一个重要的观察模式串自己跟自己匹配假设当前匹配到了text的第i个位置模式串的指针停在j这个下标也就是说text[i-j]到text[i-1]这一段已经和pattern[0]到pattern[j-1]完全一致。现在text[i]和pattern[j]出现了失配。这时候我们手上的信息是已经匹配的这j个字符和pattern开头的j个字符是一模一样的。那么问题来了如果这j个字符的“尾部”和pattern开头的某一段也相同我们就可以把pattern串直接平移过来让那段相同的前缀对齐后继续比较。举个例子。pattern是ABABCABAB假设我们已经匹配到j4也就是前4个字符ABAB都匹配成功了在第5个字符C的位置失配。这4个字符ABAB里面后缀AB和前缀AB是相同的。因此我们可以认为pattern的前两个字符AB已经和文本当前位置前方的AB对齐了不需要再把文本指针回退到头重新比较只需要把模式串指针从4改成2然后继续比较text[i]和pattern[2]就行。这个逻辑听起来很直接但要落地成代码就需要一个东西来记录“每个位置失配时pattern应该跳到哪个下标”。这就是next数组也叫前缀函数数组。2.2 next数组到底存了什么next数组有很多种定义方式不同教材里的下标习惯还不一样我看过最让人混淆的是把next[1]定义为第一个字符失配时的跳转位置。这里我采用一种最贴近工程实现的定义next[j]表示当pattern[j]这个位置失配时模式串指针应该跳到的新下标。换句话说如果已经匹配成功了pattern的前j个字符而第j1个字符对不上那模式串指针不是归零也不是右移一位继续试而是直接跳到next[j]。注意这里还有一个保险栓如果next[j]为-1代表连第一个字符都匹配不上主串指针就得前进一位模式串指针从0重新开始。把-1这个哨兵写进代码能省去很多边界判断。2.3 为什么主串指针可以坚决不回退这个问题我当年想了好久。KMP看起来神乎其神主串指针一趟跑完为什么不会错过答案其实证明并不复杂。失配时text在i之前已经有j个字符和pattern的前j个字符完全相等。这j个字符中最后k个字符又恰好和pattern前k个字符相等。因为text中这最后k个字符本身也是这j个字符的后缀所以当我们将pattern前k个字符对齐到这段文本上时这k个字符是完全已知且匹配的。也就是说KMP跳转后主串指针不需要回退到i-k再从头比较因为主串指针前方的k个字符已经被确认过了。它唯一不能确定的是text[i]和pattern[k]是否相等所以直接从text[i]开始比较即可。这个对齐过程没有跳过任何理论上可能产生匹配的位置所以结果不会漏。3. 手把手算 next 数组3.1 最长相等前后缀概念先行要看懂next数组的计算先得把“最长相等前后缀”这个概念搞清楚。对于一个长度为L的子串它的前缀和后缀都不允许等于它自己必须是一个正常的“真前缀”和“真后缀”。所谓最长相等前后缀就是从开头截出的一段字符和从结尾截出同样长度的一段字符内容完全一样并且尽可能长。比如ABABCABAB这个串它的前缀有A、AB、ABA、ABAB等后缀有B、AB、BAB、ABAB等。观察下来前缀AB和后缀AB一样前缀ABAB和后缀ABAB也一样其中最长的是长度为4的ABAB。在KMP里next[j]本质上记录的是pattern[0..j-1]这个前缀串的最长相等前后缀的长度。注意不是pattern[0..j]因为失配发生在第j个字符时之前已经确认匹配的是前j个字符所以要看的是那个长度为j的前缀串。3.2 拿一个真实模式串一步步写出 next我经常用ABABCABAB来演示因为这个模式串前后缀重叠得很典型而且不全是重复字母不会给人“偷懒”的感觉。它的next数组计算过程如下。我们定义子串是pattern的前j个字符即pattern[0]到pattern[j-1]逐步算j子串最长相等前后缀长度1A无02AB无03ABAA14ABABAB25ABABC无06ABABCAA17ABABCABAB28ABABCABAABA39ABABCABABABAB4这9个长度值不是直接作为next数组的我们的代码里还会在最前面加一个哨兵。用我习惯的定义方式最终得到的next数组是[-1, 0, 0, 1, 2, 0, 1, 2, 3, 4]其中next[0]对应第一个字符失配时跳到-1next[1]对应第二个字符失配时跳到0以此类推。这个数组读起来很规律但如果你自己手算一遍会发现越往后越容易数错。因为最长相等前后缀的“长度”和它在模式串里的下标很容易搞混建议和我一样先在纸上写出每个子串再用两个记号分别划出前缀和后缀最后确认它们完全一致再填长度。3.3 递推公式的精髓与 C 实现真正写代码时当然不能每算一个next[i]就重新暴力找一次最长相等前后缀那样复杂度又回到O(m^2)没有任何意义。正确做法是利用之前的计算结果递推。最经典的双指针写法如下vectorint buildNext(const string p) { int m p.size(); vectorint next(m 1, 0); next[0] -1; int i 0, j -1; while (i m) { if (j -1 || p[i] p[j]) { i; j; next[i] j; } else { j next[j]; } } return next; }这里i表示当前正在尝试扩展的位置j表示已经匹配上的前缀长度。为什么当字符相等时可以直接让next[i1]变成j1因为pattern[i]能接着pattern[j]继续匹配说明前i1个字符中存在一个长度为j1的相等前后缀。为什么字符不相等时j要回退到next[j]而不是0因为pattern[0..i]这个前缀串内部的next关系已经算好了next[j]记录的是它自己的最长相等前后缀。回退到next[j]相当于在这个较小的前缀上继续寻找可能的重叠不会跳过正确答案。我建议你上手写一遍然后把ABABCABAB的next数组手动推一遍再对比上面代码的输出。写第一遍时最容易犯的错误是在else分支里写“j j - 1”或“j 0”。前者逻辑不对后者虽然不至于错但会退化成最笨的寻找方式并且可能漏掉更长的重叠。3.4 next构建的复杂度与常见边界buildNext的时间复杂度是O(m)。为什么因为i在整个过程中只增不减最多增加m次而j虽然会不断回退但每次回退到next[j]至少会让j变小而j随后又只能通过i和j同时加1来增长。因此j的回退总次数不会超过j在整个过程中增长的总次数也就是O(m)。这是KMP构建部分线性复杂度的直观证明。这里有两个边界情况要特别留意。第一个是空模式串m为0buildNext返回的数组只有[-1]在模块外部调用匹配函数前最好单独处理。第二个是模式串长度为1此时next数组应该只有[-1, 0]匹配时如果第一个字符失配j就会变成-1主串指针前进一位。在实际工程代码里我还习惯把next数组开成m1大小而不是很多教材里的m大小。多出最后一个next[m]看起来很浪费但它能让我在匹配成功之后继续用统一的逻辑求重叠匹配避免为jm写一套特殊分支。4. KMP 主匹配完整可用的 C 实现4.1 直接可用的完整代码下面这套代码我实际在本地跑过也在线上某些日志分析场景里用过整体比较顺手#include iostream #include string #include vector using namespace std; vectorint buildNext(const string p) { int m p.size(); vectorint next(m 1, 0); next[0] -1; int i 0, j -1; while (i m) { if (j -1 || p[i] p[j]) { i; j; next[i] j; } else { j next[j]; } } return next; } vectorint kmpSearch(const string text, const string pattern) { vectorint positions; if (pattern.empty()) return positions; vectorint next buildNext(pattern); int n text.size(), m pattern.size(); int i 0, j 0; while (i n) { if (j -1 || text[i] pattern[j]) { i; j; if (j m) { positions.push_back(i - m); j next[j]; } } else { j next[j]; } } return positions; }这段代码返回的是模式串在文本里的所有起始位置。很多第一次接触KMP的人会问为什么匹配成功之后j不是重置成0而是next[j]因为如果不重置像AAAA匹配AAA这种重叠场景就会漏掉第二个匹配位置。j next[j]的意思是说即使完成了一次完整匹配我们仍然可以把这个完整模式串看作一个已经匹配失败的模式串利用它的最长相等前后缀在当前位置继续匹配。4.2 用真实例子走一遍全过程我拿text ABABDABACDABABCABAB 和 pattern ABABCABAB来演示。这个过程我建议你也跟着笔算一遍比单纯读文字要扎实得多。关键步骤记录如下i0到i3j从0走到4text前4个字符ABAB和pattern前4个字符完全相等。i4时text[4]Dpattern[4]C失配。根据next[4]2j跳到2然后比较text[4]D和pattern[2]A继续失配。再次失配j跳到next[2]0比较text[4]D和pattern[0]A失配。继续失配j跳到next[0]-1此时进入“主串指针1模式串归零”的分支i变成5。后面会继续这个循环真正找到匹配的位置是起始下标10。走到i10附近时text[10]到text[18]刚好和pattern完全相等这时j会一路从0增长到9匹配成功把位置10记录下来然后将j更新为next[9]4继续向右扫描。你把上面的步骤画成一张表格会比任何文字描述都直观。我强烈建议在草稿纸上画两行一行text一行pattern然后用一个箭头标记i一个标记j自己走一遍。KMP这个算法只有亲手走一遍才能彻底摆脱“背模板”的状态。4.3 复杂度证明以及为什么不是所有场景都碾压匹配阶段的复杂度是O(n)。主串指针i只会向右移动总共移动n次j可以回退但前面已经证明回退的总次数不超过它增长的总次数也就是不超过n。所以整体复杂度是O(nm)。空间上主要是next数组的O(m)非常节省。不过我不想把KMP吹成“天下无敌”。在工程里如果模式串很短、文本串很长且字符表较大Boyer-Moore这类以坏字符规则为主导的算法往往实际跑得更快。KMP的优势在于它对最坏情况有稳定保证尤其是模式串自相似很严重、存在大量重复字符时它的表现是最稳定的。如果你只是想在一段英文文档里找一个短单词直接调用标准库的find或者Boyer-Moore实现往往比手写KMP更合适。KMP更多是用来解决“必须自己实现且不能退化”的硬场景。5. 工程里那些坑和排查实录5.1 匹配重叠结果时别把j直接重置成0这是我见过最多人犯的错。有些版本的KMP在匹配成功后会把j归零然后继续循环。这在某些题目里没问题比如只要返回“第一次出现的位置”那确实无伤大雅。但如果你需要统计所有出现次数或者返回所有起始位置这种做法就会漏掉重叠匹配。举个例子text AAAApattern AAA。正确答案应该是位置0和位置1两个匹配。如果你匹配完位置0之后把j直接设成0那就会从i3开始下一轮比较最终只能得到位置0一个结果。正确做法是匹配成功后让j next[m]利用模式串自身的前后缀重叠继续在当前位置比较。这个细节很小但直接影响正确性。我还在实际项目里遇到过更隐蔽的版本代码把next数组开成m大小然后在j m时访问next[j]结果越界。这也是为什么我坚持开m1大小多出的那一位就是专门给这种场景准备的。5.2 空串、越界、size_t这些不起眼的麻烦C里字符串长度返回的是size_t本质上是无符号整数。KMP代码里j经常要变成-1如果你贪方便把j声明成size_t那j -1的判断会立刻变成灾难甚至可能让代码陷入死循环。我建议所有和模式串位置相关的变量都用int至少在你彻底理解KMP之前先这么写。后续如果你想做极致的性能优化再考虑其他类型也不迟。空模式串也要单独处理。我见过有人直接在buildNext里对空串调用p.size()再减1结果无限循环或者直接崩溃。kmpSearch函数开头加一句if (pattern.empty()) return positions几行代码就能避免这个坑。另外如果模式串的长度大于文本串理论上可以直接返回空结果虽然循环也能正确结束但加一个长度判断能让代码更清晰。5.3 要不要用“优化版next”影响在哪很多教材里会提到所谓的优化版next数组它和普通next的区别在于普通next在失配后跳到某个位置万一跳过去的字符和刚才失配的字符一样那还会立刻再失配一次优化版next会在构建时直接把这个“必然发生的失配”跳过让数组指向更远的位置。优化版的构建代码长这样vectorint buildNextOptimized(const string p) { int m p.size(); vectorint next(m 1, 0); next[0] -1; int i 0, j -1; while (i m) { if (j -1 || p[i] p[j]) { i; j; next[i] (p[i] ! p[j]) ? j : next[j]; } else { j next[j]; } } return next; }区别就在那句三元表达式如果跳转后的字符和待比较的字符仍然相同就继续使用next[j]否则才用j。这个优化不会改变复杂度只会少做几次无意义的比较。面试时如果讲到这一层会显得比较有深度工程上如果你能确定模式串中重复字符不多用普通版也完全没问题。我个人在写线上代码时偏向普通版因为逻辑更直白后面人维护起来不容易误操作。如果你要处理的是类似“AAAAAAAAA”这种极端重复的模式串那优化版确实能带来肉眼可见的收益。6. 从 next 数组再往前一步推荐练习与延伸思路6.1 一个很好的自查题统计每个前缀出现次数KMP学完之后我推荐你做一个看似不难但很考验理解的题目给一个模式串统计每个前缀在它自身中出现的次数。这个题可以通过next数组倒序累计来解决。思路是这样的先把next数组构建出来然后把每个位置i对应的前缀初始计数值设为1再倒序遍历i令cnt[next[i]]累计上cnt[i]。为什么要倒序因为next数组天然形成一棵类似树的结构每个节点都指向它的最长相等前后缀节点。正序遍历会丢失祖先节点的叠加信息倒序则保证每个节点的后代都先累加完毕。这个练习对理解前缀函数的本质特别有帮助做完以后你会更清楚地看到next数组不是一堆孤立的跳转值而是一张可以支撑很多动态规划计算的“失配关系网”。6.2 延伸方向Z算法、AC自动机和更多工程选择KMP不是字符串算法的终点。Z算法能在O(n)时间内求出每个位置和字符串开头的最长公共前缀长度它和KMP在思想上是相通的代码结构甚至比KMP更好写。如果你要做多模式匹配也就是同时匹配多个敏感词、多个关键词那么AC自动机才是正解它本质上就是“建在Trie树上的KMP”把单个模式串的next数组推广成了多模式共享的状态转移。如果你更关注实际工程性能那Boyer-Moore和Horspool这类“坏字符为主、好后缀为辅”的算法也值得了解。它们在大字符集、短模式的场景下通常跑得更快。不过我依然建议你先把KMP的来龙去脉搞清楚因为KMP是理解其他字符串匹配算法的一把钥匙。各种算法的取舍不是非此即彼完全取决于你的模式和文本特征。6.3 最后分享一点个人体会我最初学KMP时在next数组上卡了很久后来发现突破点不在于把公式背下来而在于接受一个反直觉的事实一旦失配我们要做的不是回看“文本串前面还差多少”而是回看“模式串前面已经匹配的部分后缀和前缀能重叠多少”。这个视角转换直接决定了代码的简洁程度和正确性。后来我做日志流匹配的时候每次遇到性能瓶颈就会想起KMP提醒自己别急着暴力重复扫描先想想哪些已知信息还能复用。技术会迭代但这种“不重复已做工作”的思路放到很多东西上都不会过时。