1. 项目概述为什么我们需要KMP算法如果你写过字符串查找的代码大概率是从一个简单的暴力匹配Brute-Force开始的。想象一下你有一本厚厚的书主串想在里面找到一句特定的话模式串。最笨的办法就是从第一页第一行开始一个字一个字地对一旦发现对不上就把书签往后挪一个字再从头开始对。这个方法简单直接但效率低下尤其是在那句话很长或者书特别厚的时候。最坏情况下它的时间复杂度是 O(m*n)m 和 n 分别是主串和模式串的长度。当数据量上来这种“暴力”就显得力不从心了。KMP算法由 Knuth、Morris 和 Pratt 三位大神共同提出就是为了解决这个效率痛点。它的核心思想是当某次匹配失败时我们已经知道了主串中当前失败位置之前的部分内容利用这些“已知信息”可以智能地跳过一些绝对不会成功的匹配尝试从而将模式串向后“滑动”多位而不是仅仅一位。这就像你在校对一段话时发现从某个词开始出错了。一个聪明的校对者不会只把光标往后移一个字符重新开始而是会快速扫描已经看过的部分找到一个可能重新开始匹配的“新起点”。KMP算法就是让计算机拥有了这种“智能回溯”的能力。对于文本编辑器中的查找、IDE中的代码搜索、杀毒软件的特征码匹配乃至生物信息学中的DNA序列比对KMP及其思想变种都是基石般的存在。网上关于KMP的教程很多但不少要么陷入复杂的数学公式推导让人望而生畏要么代码和原理脱节看了之后“好像懂了一写就废”。本文的目标是用最直观的图解和手把手的代码注解帮你彻底打通KMP的任督二脉。我们会从暴力匹配的痛点出发一步步引出“最长相等前后缀”和next数组这两个核心概念并用实例让你亲眼看到模式串是如何“跳跃”的。最后我们会提供C和C语言两种版本的详细实现和注解并附上我调试时踩过的坑和心得。相信我读完本文你关于KMP的所有疑惑都将得到解答。2. 核心思想拆解从暴力匹配到智能跳跃2.1 回顾暴力匹配的困境我们先写一个简单的暴力匹配函数用它来直观感受问题所在。假设我们要在主串S “ABABCABABD”中查找模式串P “ABABD”。暴力匹配的C代码片段如下int bruteForce(const string s, const string p) { int n s.length(), m p.length(); for (int i 0; i n - m; i) { // i是主串的起始匹配位置 int j; for (j 0; j m; j) { if (s[i j] ! p[j]) { // 逐个字符比较 break; // 发现不匹配跳出内层循环 } } if (j m) { // 内层循环完整走完说明匹配成功 return i; // 返回匹配起始位置 } // 匹配失败i相当于模式串右移一位 } return -1; // 未找到 }用我们的例子走一遍第一轮S[0-4](“ABABC”) 与P(“ABABD”) 比较。前四个字符 “ABAB” 都匹配到第五个字符S[4](‘C’) !P[4](‘D’)失败。第二轮i1从S[1](‘B’) 开始与P[0](‘A’) 比较第一个字符就失败。第三轮i2从S[2](‘A’) 开始与P比较。S[2](‘A’) P[0](‘A’)S[3](‘B’) P[1](‘B’)S[4](‘C’) !P[2](‘A’)失败。… 如此反复。你会发现在第一次失败时我们已经知道S[0..3](“ABAB”) 和P[0..3](“ABAB”) 是匹配的。但暴力匹配完全丢弃了这些信息在第二轮匹配中它又傻傻地从S[1](‘B’) 和P[0](‘A’) 开始比较这显然是徒劳的因为我们已经知道S[1]是 ‘B’而模式串开头是 ‘A’根本不可能匹配。注意这里就是KMP算法的发力点。KMP会问既然S[0..3](“ABAB”) 已经匹配成功而这个子串本身有什么特点能否利用这个特点直接确定下一个可能匹配的起始位置跳过那些绝对不可能成功的尝试2.2 KMP的智慧利用“已知信息”避免回溯KMP算法不让主串的指针i回溯。在上面的例子中第一轮匹配失败在S[4](‘C’) 和P[4](‘D’)。此时i仍然停留在4指向‘C’而模式串的指针j在4指向‘D’且匹配失败。关键问题来了接下来模式串应该从哪里开始和S[4](‘C’) 继续比较或者说j应该回退到模式串的哪个位置KMP的答案是回退到模式串P中已匹配成功的前缀子串 (P[0..j-1]即“ABAB”) 的“最长相等前后缀”的长度所指示的位置。这里引入了两个核心概念前缀和后缀对于字符串 “ABAB”它的前缀有”A”, “AB”, “ABA”它的后缀有”B”, “AB”, “BAB”。注意前缀和后缀都不包括字符串本身。最长相等前后缀找出既是前缀又是后缀的最长子串。对于 “ABAB”长度为1前缀”A”后缀”B”不等。长度为2前缀”AB”后缀”AB”相等。长度为3前缀”ABA”后缀”BAB”不等。 所以“ABAB” 的最长相等前后缀是 “AB”其长度为2。这个长度 “2” 就是我们的钥匙。它意味着在已匹配的 “ABAB” 中末尾的 “AB” 和开头的 “AB” 是相同的。既然主串S中i指针前的部分即S[2..3]也就是“AB”和模式串P开头部分P[0..1]也是“AB”相同那我们就可以把模式串的开头“AB”滑动到与主串的“AB”对齐的位置然后从P[2]开始与S[4]继续比较。图解过程第一轮匹配失败时 主串 S: A B A B C A B A B D i4 (指向C) 模式串 P: A B A B D j4 (指向D匹配失败) 已匹配部分: “ABAB” “ABAB”的最长相等前后缀是“AB”(长度2)。 第二轮KMP智能跳跃后 主串 S: A B A B C A B A B D i4 (不动) 模式串 P: A B A B D j2 (回退到2指向A) 现在比较 S[4](C) 和 P[2](A)。看主串指针i没有动我们只是把模式串的指针j从4回退到了2。这相当于把整个模式串P向右移动了j - next[j] 4 - 2 2位。我们跳过了i1和i2这两个绝无可能成功的起始位置。2.3 Next数组预处理的“跳跃表”显然对于模式串的每一个位置j当匹配失败时我们都需要知道如果当前位置匹配失败j应该回退到哪个位置这个“回退位置”信息我们预先计算好存储在一个数组中这个数组就是大名鼎鼎的next数组有些实现也叫fail或lps数组。next[j]的定义是当模式串中第j个字符P[j]与主串失配时模式串需要跳转到哪个位置新的j继续与主串当前字符进行比较。如何求next数组它的求法本质上是在模式串P内部进行的一次“自我匹配”寻找每个前缀子串的最长相等前后缀长度。有一个非常巧妙且高效的方法其核心代码和KMP匹配主流程几乎一模一样。手动计算next数组以 P“ABABD” 为例我们约定next[0] -1表示如果模式串第一个字符就匹配失败那么主串指针i前进一位模式串j重置为0通过j next[j]即j -1后在循环中会执行j和i实现。j0:next[0] -1。j1: 前缀 “A”最长相等前后缀长度为0next[1] 0。j2: 前缀 “AB”最长相等前后缀长度为0next[2] 0。j3: 前缀 “ABA”最长相等前后缀是 “A”长度为1next[3] 1。j4: 前缀 “ABAB”最长相等前后缀是 “AB”长度为2next[4] 2。所以对于P“ABABD”next数组为[-1, 0, 0, 1, 2]。实操心得很多初学者对next数组的求法感到困惑特别是那个“用模式串匹配自己”的过程。一个有效的理解方法是把求next数组的过程想象成有两个相同的模式串P一个作为“主串”下标i从1开始一个作为“模式串”下标j从0开始然后进行KMP匹配。当“主串”的P[i]和“模式串”的P[j]匹配时next[i]的值就和j有关。这个类比能很好地统一匹配和预处理的过程。3. 算法实现与代码逐行注解理解了思想我们来看代码。我会提供两个版本的详细实现一个是C风格使用string一个是C风格使用字符数组并附上逐行注解。3.1 C版本实现#include iostream #include vector #include string using namespace std; /** * 构建模式串P的next数组。 * param p 模式串 * param next 用于存储next数组的vector长度应为p.size() * 时间复杂度O(m) m为模式串长度。 */ void getNext(const string p, vectorint next) { int m p.size(); next.resize(m); next[0] -1; // 约定俗成第一个字符失配j重置为-1随后会1变成0 int j -1; // 指向前缀的末尾位置同时也是已匹配的长度 int i 0; // 指向后缀的末尾位置 while (i m - 1) { // 注意是 m-1因为next[i]表示p[i]匹配失败时的回退位置 // 注解1如果 j -1说明要重新开始匹配或者当前字符匹配成功 if (j -1 || p[i] p[j]) { // i和j都向后移动一位 i; j; // 注解2这是最核心的赋值。next[i] j 意味着 // 当p[i]匹配失败时可以跳转到p[j]继续尝试。 // 因为p[0...j-1] 和 p[i-j...i-1] 是相等的。 next[i] j; } else { // 注解3如果p[i] ! p[j]说明失配。 // 此时j需要回退到next[j]的位置继续尝试匹配p[i]。 // 这其实就是KMP匹配过程在模式串内部的运用。 j next[j]; } } } /** * KMP主匹配函数。 * param s 主串 * param p 模式串 * return 模式串在主串中首次出现的起始下标未找到返回-1。 * 时间复杂度O(nm) n为主串长度m为模式串长度。 */ int kmpSearch(const string s, const string p) { int n s.size(), m p.size(); if (m 0) return 0; // 模式串为空约定返回0 if (n m) return -1; // 主串比模式串短肯定找不到 vectorint next(m); getNext(p, next); // 预处理next数组 int i 0; // 主串指针 int j 0; // 模式串指针 while (i n j m) { // 注解4匹配成功或者j-1模式串第一个字符就失配指针都后移 if (j -1 || s[i] p[j]) { i; j; } else { // 注解5匹配失败模式串指针j根据next数组回退 // 主串指针i不动 j next[j]; } } // 循环结束判断是否匹配成功 if (j m) { return i - j; // 返回匹配起始位置 } else { return -1; } } int main() { string s ABABCABABD; string p ABABD; int pos kmpSearch(s, p); if (pos ! -1) { cout Pattern found at index: pos endl; } else { cout Pattern not found. endl; } // 输出next数组验证 vectorint next; getNext(p, next); cout Next array: ; for (int val : next) cout val ; cout endl; return 0; }代码关键点注解getNext函数中的if (j -1 || p[i] p[j])j -1是一个边界条件它发生在两种情况下a) 刚开始i0, j-1b) 在else分支中j next[j]不断回退直到j回退到-1。这表示对于当前后缀末尾p[i]找不到任何相等的前缀与之对应因此next[i1]应该为0通过i; j; next[i]j;实现此时j从-1变为0。next[i] j的时机这条语句是在i和j自增之后执行的。这意味着next[i]记录的是当p[i]匹配失败时j应该回退到的位置。因为在上一步p[i-1]和p[j-1]是匹配的所以p[0...j-1]等于p[i-j...i-1]。这是一个需要仔细体会的点。j next[j]这是KMP思想的精髓在预处理阶段的体现。当p[i] ! p[j]时我们不把i回溯而是让j回退到next[j]的位置继续尝试与p[i]匹配。这保证了预处理过程也是O(m)的时间复杂度。主函数中的if (j -1 || s[i] p[j])和预处理逻辑一致。j -1表示模式串已经回退到起点之前说明主串当前字符s[i]与模式串开头都无法匹配那么主串和模式串的指针都应该向后移动一位i; j;使得j从-1变为0。j next[j]匹配失败时的核心操作。根据预处理好的“地图”next数组直接跳到下一个可能匹配的位置主串指针i原地等待。3.2 C语言版本实现对于嵌入式、内核开发或追求极致性能的场景C语言版本更直接。#include stdio.h #include string.h #include stdlib.h /** * 构建next数组 (C风格) * param p 模式串指针 * param next 用于存储next数组的指针调用者需分配足够内存 (长度strlen(p)) * return 无 */ void getNext_c(const char* p, int* next) { int m (int)strlen(p); next[0] -1; int j -1; int i 0; while (i m - 1) { if (j -1 || p[i] p[j]) { i; j; next[i] j; } else { j next[j]; } } } /** * KMP搜索 (C风格) * param s 主串指针 * param p 模式串指针 * return 首次匹配位置指针未找到返回NULL */ const char* kmpSearch_c(const char* s, const char* p) { int n (int)strlen(s); int m (int)strlen(p); if (m 0) return s; // 空串是任意串的子串 if (n m) return NULL; int* next (int*)malloc(m * sizeof(int)); if (!next) return NULL; // 内存分配失败处理 getNext_c(p, next); int i 0; // 主串下标 int j 0; // 模式串下标 while (i n j m) { if (j -1 || s[i] p[j]) { i; j; } else { j next[j]; } } free(next); // 释放动态分配的next数组 if (j m) { return s (i - j); // 返回匹配起始位置的指针 } else { return NULL; } } int main() { const char* s ABABCABABD; const char* p ABABD; const char* result kmpSearch_c(s, p); if (result) { printf(Pattern found at position: %ld\n, result - s); } else { printf(Pattern not found.\n); } // 手动计算并打印next数组 int m (int)strlen(p); int* next (int*)malloc(m * sizeof(int)); getNext_c(p, next); printf(Next array: ); for (int i 0; i m; i) printf(%d , next[i]); printf(\n); free(next); return 0; }C版本注意事项内存管理next数组需要在堆上动态分配使用后务必free防止内存泄漏。这是与Cvector自动管理内存的主要区别。字符串长度使用strlen获取长度注意其时间复杂度是O(n)在性能敏感循环中应避免重复调用。这里在函数开头计算一次并存储。返回值返回的是匹配位置的指针 (const char*)这比返回下标更符合C语言处理字符串的惯例。通过result - s可以得到下标。错误处理增加了对malloc失败的简单检查在实际工程代码中需要更完善的错误处理机制。4. Next数组的优化NextVal数组我们上面构建的next数组有一个小瑕疵。看这个例子主串S“AAAAB”模式串P“AAAA”。模式串P的next数组为[-1, 0, 1, 2]。匹配过程i0,j0:S[0]‘A’, P[0]‘A’匹配i1,j1。i1,j1:S[1]‘A’, P[1]‘A’匹配i2,j2。i2,j2:S[2]‘A’, P[2]‘A’匹配i3,j3。i3,j3:S[3]‘A’, P[3]‘A’匹配i4,j4。此时jm匹配成功。现在考虑在S“AAABAAAAB”中查找P“AAAA”。当匹配到i3, j3时S[3]‘B’, P[3]‘A’失配。根据next[3]2j回退到2。此时比较S[3]‘B’和P[2]‘A’依然失配。根据next[2]1j回退到1。比较S[3]‘B’和P[1]‘A’依然失配。根据next[1]0j回退到0。比较S[3]‘B’和P[0]‘A’依然失配。根据next[0]-1j变为-1然后执行i, j变成i4, j0。发现问题了吗当P[3]失配时由于P[3]、P[2]、P[1]、P[0]都是 ‘A’所以S[3](‘B’) 和它们比较都会失败。我们进行了多次无意义的回退和比较。优化思路如果在计算next数组时发现P[j]和P[next[j]]是相同的字符那么当P[j]失配时跳转到P[next[j]]肯定也会失配因为字符相同。那么我们可以直接跳到next[next[j]]以此类推。我们可以把这个优化信息直接存储到next数组中得到优化后的nextval数组。计算nextval数组的方法 在计算next数组的基础上多一步判断void getNextVal(const string p, vectorint nextval) { int m p.size(); nextval.resize(m); nextval[0] -1; int j -1, i 0; while (i m - 1) { if (j -1 || p[i] p[j]) { i; j; // 优化点比较 p[i] 和 p[j] if (p[i] ! p[j]) { nextval[i] j; // 字符不同和next数组一样 } else { nextval[i] nextval[j]; // 字符相同直接继承nextval[j]的值 } } else { j nextval[j]; } } }对于P“AAAA”next数组[-1, 0, 1, 2]nextval数组[-1, -1, -1, -1]解释nextval[1]因为p[1]p[0]‘A’所以nextval[1] nextval[0] -1。同理nextval[2] nextval[1] -1nextval[3] nextval[2] -1。使用nextval数组进行匹配当P[3]失配时j nextval[3] -1然后直接i, j一步到位跳过了所有无意义的比较。在模式串中有很多连续重复字符时nextval数组能显著提升效率。注意事项nextval是next的优化版本理解next是根本。在面试或初学实现时能写出正确的next数组构建和KMP匹配就已经很棒了。在实际工程中如果模式串重复度高使用nextval是更好的选择。很多教材和文章将优化后的数组直接称为next数组需要注意区分其具体含义。5. 复杂度分析与应用场景5.1 时间复杂度分析预处理阶段构建next数组时间复杂度为O(m)其中m是模式串长度。虽然代码中有两层循环的错觉while和内部的if-else但注意j的值在j next[j]时是在减少而i在单调增加。j减少的总次数不可能超过它增加的总次数每次匹配成功j而j增加的总次数不超过m。因此整个预处理过程是线性的。匹配阶段时间复杂度为O(n)其中n是主串长度。同理主串指针i只增不减模式串指针j虽然会因失配而回退但回退的总步数也不会超过前进的总步数。i和j的变化总次数与n成线性关系。总时间复杂度O(n m)。这比暴力匹配的 O(n*m) 要好得多尤其是在主串很长模式串也不短的情况下优势巨大。5.2 空间复杂度分析需要额外一个大小为m模式串长度的整型数组来存储next或nextval信息。因此空间复杂度为O(m)。5.3 典型应用场景单模式串匹配这是KMP最直接的应用如文本编辑器中的“查找”功能。字符串查找库函数许多编程语言标准库中的字符串查找函数如C的strstr C的string::find在底层可能会使用KMP或其变种如Boyer-Moore, Sunday算法等来实现高效匹配。循环节判断利用next数组可以高效判断一个字符串是否有循环节以及最小循环节的长度。对于一个长度为n的字符串如果n % (n - next[n]) 0则该字符串由长度为n - next[n]的子串循环构成。前后缀问题next数组本身记录了每个前缀的最长相等前后缀长度可以用于解决一些与字符串前后缀相关的问题。更复杂算法的基础KMP是许多高级字符串算法如AC自动机的核心组成部分。AC自动机可以看作是KMP在多模式串匹配上的扩展。6. 常见问题与调试技巧实录即使理解了原理亲手实现时也难免遇到问题。下面是我在学习和教学过程中总结的几个常见坑点和调试技巧。6.1 数组越界问题这是实现KMP时最容易出现的运行时错误。getNext函数中的越界while (i m - 1) { // 正确写法 // while (i m) { // 错误写法当im-1时执行i后imnext[i]会越界。因为我们在if分支里先执行了i然后才next[i] j。所以循环条件必须保证i在自增后小于m。因此使用i m - 1作为条件。next数组访问越界在j next[j]时必须确保j是有效的下标。我们的实现中next[0] -1而j在变为-1后会在if条件中判断j -1并进入分支从而避免了对next[-1]的访问。这是一个巧妙的边界处理。调试技巧在getNext函数中在next[i] j和j next[j]语句前后打印i,j,next[i]的值观察其变化是否符合预期。对于C语言版本要确保malloc分配的空间足够大。6.2 Next数组值理解错误next[j]表示当P[j]匹配失败时j应该跳转到的新位置。很多人误以为next[j]是最长相等前后缀的长度。对于我们的定义next[0] -1next[j]确实等于“P[0...j-1]这个子串的最长相等前后缀长度”。但注意这个值就是跳转后的新j。有些教材定义next[0] 0并将next[j]直接定义为长度那么在跳转时就需要j next[j-1]。务必明确你使用的next数组定义并在匹配逻辑中保持一致。建议采用next[0] -1的定义代码更简洁边界处理更统一。这也是本文采用的约定。6.3 匹配失败条件与循环控制匹配主循环的结束条件while (i n j m)和结束后的判断if (j m)是标准写法。但要注意如果模式串为空 (m0)应该直接返回0表示在起始位置找到空串。这是一个特例需要在函数开头处理。循环内部的if (j -1 || s[i] p[j])分支处理了两种推进情况一是彻底失配后重置j二是字符匹配成功。6.4 性能测试与对比编写一个简单的测试程序用暴力匹配和KMP算法分别在同一对长主串和模式串上进行搜索并计时。#include chrono // ... 省略bruteForce和kmpSearch函数 ... int main() { // 构造一个较长的字符串和模式 string s(1000000, A); // 100万个A s B; string p(10000, A); // 1万个A p B; auto start chrono::high_resolution_clock::now(); int pos1 bruteForce(s, p); auto end chrono::high_resolution_clock::now(); auto duration_bf chrono::duration_castchrono::microseconds(end - start); start chrono::high_resolution_clock::now(); int pos2 kmpSearch(s, p); end chrono::high_resolution_clock::now(); auto duration_kmp chrono::duration_castchrono::microseconds(end - start); cout Brute-Force found at: pos1 , time: duration_bf.count() us endl; cout KMP found at: pos2 , time: duration_kmp.count() us endl; return 0; }在这个例子中暴力匹配需要回退主串指针近100万次而KMP几乎可以一次比较就滑到最后性能差异会非常明显。通过实际测试你能直观感受到算法优化带来的威力。6.5 理解上的“最后一公里”很多朋友卡在“为什么求next数组的代码和匹配的代码如此相似”这一点上。我提供一个终极类比KMP匹配是模式串P在主串S上“爬行”利用next数组决定滑多远。求next数组是模式串P在自己身上“爬行”我们把P既当作主串从下标1开始又当作模式串从下标0开始寻找每个位置之前子串的自我相似性最长相等前后缀。这个过程本质上就是一个自我匹配的过程所以代码结构高度一致。最后学习KMP最好的方式就是拿出纸笔手动模拟一遍getNext和kmpSearch的过程选择一个简单的例子如S“ABABCABABD”, P“ABABD”一步步写下i,j,next数组的变化。当你能够不借助代码独立完成这个模拟时KMP算法就真正属于你了。这个算法初次接触会觉得绕但一旦想通那种豁然开朗的感觉和对计算机科学家智慧的钦佩会是编程学习路上一次美妙的体验。