我们总是和找东西打交道。在代码里最常见的就是在一个很长的字符串里找一个短字符串比如在一整本《三体》的文本里统计汪淼出现过多少次。最直观的做法是暴力匹配从第一个字符开始试不匹配就整体往后挪一位再试直到找到为止。这个办法在绝大多数场景下其实够用但一旦文本有几十兆、模式串有几千个字符暴力匹配的短板就暴露无遗——它会在看似快要成功的位置反复做无用功。KMP 算法Knuth-Morris-Pratt 算法解决的正是这个问题。它通过预处理模式串构造一张失配跳转表即 next 数组让匹配过程在主串指针不回退的前提下完成查找。也就是说匹配过程中主串的索引始终向前绝不倒退最坏情况下时间复杂度稳定在 O(mn)其中 m 是主串长度n 是模式串长度。这比暴力匹配的 O(m×n) 要扎实得多。这篇文章我会从一个真实的匹配场景切入先带你看清楚暴力匹配到底慢在哪里再手把手拆解 next 数组的构造逻辑和手算技巧最后给出可直接复用的代码实现并且把 KMP 能做的那些隐性应用也串一遍。无论你是刚接触算法的初学者还是在刷题或做文本处理时被字符串匹配卡过的人这篇文章都值得读完。1. 暴力匹配的致命循环为什么它总在重复劳动先说清楚一个概念字符串匹配的任务是给定一个主串 S长度 m和一个模式串 P长度 n找到 P 在 S 中第一次出现的位置如果 P 没出现则返回 -1。暴力匹配的思路非常直白从 S 的第 0 位开始把 P 的首字母和 S[i] 对齐然后逐个比较。如果中间某个字符不匹配就把 P 整体向右移动一位也就是让 S[i1] 和 P[0] 对齐再重新比较。这种做法的关键在于每一次失配后主串指针和模式串指针都要回到起点重来。我用一个非常典型的例子来说明问题。假设主串 S aaaaaaaaaaaaaaaaaaaaaaab一长串 a结尾一个 b模式串 P aaaaab。暴力匹配的过程大致是这样从 S[0] 开始P 的 5 个 a 都匹配但 P[5] 是 bS[5] 是 a失配。然后从 S[1] 开始重复上述过程又是 5 个 a 匹配到了但 P[5] 和 S[6] 失配。一直这样循环直到主串指针挪到倒数第 6 个字符才有可能让 P[5] 对上那唯一的 b。在这个过程里每次失配后主串指针和模式串指针都回退到相对位置的起点从模式串的第一个字符重新比较。主串有 m 个字符模式串有 n 个字符最坏情况下每次都要比较 n 次再移动 m-n1 次总比较次数接近 (m-n1)×n也就是 O(m×n)。这里最浪费的是什么是信息的丢弃。你在第五个字符上失配说明前四个字符是什么你已经知道了。但暴力匹配的处理方式是把前面比较过的信息全部扔掉重新来一遍。如果模式串本身存在重复的前缀和后缀这种浪费就更明显——明明主串后面的一部分已经和模式串的前缀长得一样你却非要把它当作全新的起点去比。生活化类比这就像你在一段路上找钥匙你往前走了一段发现没有然后回到起点从你上一次检查过的位置旁边再从头找一遍而不是在原地记住刚检查过这段可以跳过继续往下推进。KMP 的核心思想本质上就是把这个已有的比较信息利用起来。具体怎么做下面开始拆解。2. 理解 next 数组是理解 KMP 的分水岭在展开 next 数组之前我先带你思考一个问题当失配发生时我们到底希望发生什么假设主串 S 在位置 i、模式串 P 在位置 j 发生了失配也就是 S[i] ! P[j]而 S[i-j ... i-1] 这一段已经和 P[0 ... j-1] 完全一致。此时我们已经知道的信息是主串中的当前窗口内容和模式串的前 j 个字符完全相同。如果我们还像暴力匹配那样回到 P[0] 重新比较那么主串指针要回退到 i-j1 的位置。但是回退之后S[i-j1] 和 P[0] 的比较结果其实早就知道了吗不一定因为 P[0] 未必等于 P[1]所以 S[i-j1] 和 P[0] 的关系是未知的必须重新比较。可如果模式串本身有某种自相似的结构情况就不一样了。比如 P abababc当在 P[5] c 处失配时前面已匹配的是 ababa。此时你仔细看P 的前缀 aba 等于已匹配部分的后缀 aba。这意味着什么意味着主串窗口往前看从当前位置往前数的 3 个字符 aba和模式串开头的 aba 是相同的没必要重新比较。我们可以直接把模式串拉到前缀等于后缀的位置继续匹配。那么前缀等于后缀这个关系需要为模式串的每个位置都提前算出来。这就是 next 数组要做的事。所以 next 数组的含义严谨地说应该是对于模式的每个位置 jnext[j] 表示当 P[j] 失配时j 应该回退到的位置。而这个位置正好与P[0 ... j-1] 的最长相同真前后缀长度相关。举个例子。设 P abababc。P[0 ... 4] ababa它的最长相同真前后缀是 aba长度为 3。所以当 P[5] c 失配时j 应该回退到 3也就是让 P[3] a 和当前主串字符继续比较。为什么不是回退到 0因为主串当前位置往前数的 3 个字符已经确定等于 aba回退到 3 可以用掉这三个匹配成果不用白白浪费。你可能会想如果回退到 3 之后还是失配怎么办那就再看 next[3]——也就是 P[0 ... 2] aba 的最长相同真前后缀长度为 1于是 j 再从 3 变成 1。这就是 KMP 匹配过程中j 不断跳转的机制。这里有个容易绕晕的概念next[j] 指的是模式串下标为 j 的字符失配后j 要跳到哪它由P[0 ... j-1]不包含 P[j]这个子串的最长相同前后缀长度决定。这个细节非常关键很多教材里写的是 next[j] 最长相等前后缀长度但实际上如果你把 next 的定义理解成跳跃目的地写代码时会少很多弯路也不容易和最朴素的前缀函数混淆。那到底怎么算这个 next 呢往下看。2.1 手算 next 数组一个可复用的三步法手算 next 数组是很多人学 KMP 时最头疼的事情。我总结了一个三步法比死记硬背公式有效得多。第一步对每个位置 j取出子串 P[0 ... j-1]。第二步找这个子串的最长相同真前后缀长度。第三步把这个长度记为 next[j]。这里特别强调真前后缀真前缀是不包含字符串最后一个字符的前缀真后缀是不包含字符串第一个字符的后缀。也就是说一个长为 L 的字符串它的真前后缀最长也只有 L-1不能拿整个子串自己和自己比。我拿一个经典模式串 P ababc 完整算一遍。j 0 时P[0 ... -1] 是空串没有前缀也没有后缀。通常人为规定 next[0] -1。这个 -1 是一个哨兵表示连模式串的第一个字符都匹配不上主串指针必须前进模式串指针回到 0。j 1 时P[0 ... 0] a只有一个字符真前后缀都为空长度为 0。所以 next[1] 0。j 2 时P[0 ... 1] ab前缀有 a后缀有 b不相等长度为 0。next[2] 0。j 3 时P[0 ... 2] aba前缀有 a、ab后缀有 ba、a最长相等的是 a长度为 1。next[3] 1。j 4 时P[0 ... 3] abab前缀有 a、ab、aba后缀有 bab、ab、b最长相等的是 ab长度为 2。next[4] 2。所以 P ababc 的 next 数组是 [-1, 0, 0, 1, 2]。这个数组怎么用当 P[j] 失配时就让 j next[j]把模式串整体右移到已匹配部分的前缀对准已匹配部分的后缀的位置如果 j -1说明模式串首位都对不上主串指针加 1j 置 0。2.2 为什么 next 要取最长而不是任意一个相等前后缀这是一个值得想明白的问题。假设 P[0 ... j-1] 既存在长度为 2 的相等前后缀也存在长度为 1 的相等前后缀为什么要选最长原因在于失配跳转的目的是在保证正确的前提下尽量少地回退模式串。跳转后模式串的前缀要覆盖住主串已匹配部分的后缀这个覆盖越长主串上已经被确认过的字符就越多后续需要重新比较的字符就越少整体效率自然越高。用更严谨的话说取最长相等前后缀实质上是保证在失配时模式串不会错过任何可能匹配的位置。如果取短了可能把本来已经在主串上对齐了的前缀浪费掉增加无谓的比较。在任何失配情况下跳转到最长相等前后缀对应的位置是理论上最优的选择。3. next 数组的代码实现从递归思想到迭代写法手算清楚了代码怎么写不少教程喜欢直接甩一个 for 循环出来说这就是 next 的求法。但如果你没想明白为什么能这样算后面调试起来很容易懵。计算 next 的核心思路其实是动态规划式的递推假设我们已经知道 next[j] 的值能不能快速推出 next[j1]推导过程是这样的。令 k next[j]也就是说 P[0 ... k-1] P[j-k ... j-1]且 k 是最大满足这一条件的前缀长度。现在要看 P[j] 这个新字符能不能让相等前后缀长度进一步增加。有两种情况如果 P[k] P[j]那么 P[0 ... k] P[j-k ... j]最大相等前后缀长度就是 k1。所以 next[j1] k1。如果 P[k] ! P[j]就说明当前的前缀延伸不下去了。此时要找的是 P[0 ... j] 的次长相等前后缀。这个次长长度是多少正好是 next[k]。因为 P[0 ... k-1] 的最长相等前后缀长度就是 next[k]它同时也刻画了 P[j-k ... j-1] 的最长相等前后缀结构。所以你看到了一个关键的递归不匹配时k next[k]然后继续比较 P[k] 和 P[j]。这本质上就是 KMP 匹配过程本身——用模式串的前缀部分去匹配模式串后缀部分这也就是为什么 next 数组的计算看起来像是一个模式串自己匹配自己的过程。基于这个推演代码其实很简单。我用 Python 写一个版本便于阅读理解def build_next(p): n len(p) nxt [-1] * n j 0 k -1 # j 表示正在计算 next[j]k 表示当前最长相等前后缀长度 while j n - 1: if k -1 or p[j] p[k]: j 1 k 1 nxt[j] k else: k nxt[k] return nxt这个实现里初始时 next[0] -1k -1j 0。循环里每次比较 P[j] 和 P[k]相等说明下一对字符也能形成更长的相等前后缀于是 j1、k1记录 next[j] k。不相等就把 k 退回 next[k]寻找次长相等前后缀如果退到 -1说明没有相等前后缀next[j1] 0然后继续。你可以拿 P ababc 手动模拟一遍这个循环输出的 next 数组和手算的完全相同。这里我要提一个大多数教程不会刻意讲的细节在很多 C/C 代码里你还会看到另一种 next 数组值是上面这种 next 整体减 1。比如 [-1, -1, -1, 0, 1]。这种写法常见于《数据结构》教材和某些竞赛代码中它的含义变成了失配后 j 回退到的位置再往前一位。两种定义没有优劣之分都能得到正确的匹配结果问题在于如果你把一个版本的代码和另一个版本的 next 数组混着用就会立刻出现莫名其妙的下标越界或者死循环。正确的做法是选定一种定义全套代码配套到底。就我个人经验而言理解上最省力的是上面这种next[j] 直接表示失配后 j 跳到哪所以下文代码和说明都采用这个约定。4. KMP 匹配过程完整模拟主串指针到底是怎么做到不回退的有了 next 数组匹配过程的逻辑就特别清晰了。我直接给出匹配函数def kmp_search(s, p): nxt build_next(p) i 0 # 主串 s 的指针 j 0 # 模式串 p 的指针 while i len(s) and j len(p): if j -1 or s[i] p[j]: i 1 j 1 else: j nxt[j] if j len(p): return i - j return -1这段代码的执行规则只有三条如果 j -1说明模式串第一个字符就和主串当前位置对不上此时主串指针前进模式串从头开始i 1, j 0。如果 S[i] P[j]两边指针同时前进继续比较下一对字符。否则失配模式串指针跳转j next[j]。你注意看整个匹配过程中主串指针 i 只增不减从不回退。这也是 KMP 算法名称里那个K所代表的 Knuth 在提出这个优化时的核心洞察——不让主串指针回头。我拿一个具体场景走一遍方便你真的看懂。主串 S abababcabababd模式串 P ababd。P 的 next 数组为 [-1, 0, 0, 1, 2]。i0, j0S[0]aP[0]a相等i1, j1。i1, j1S[1]bP[1]b相等i2, j2。i2, j2S[2]aP[2]a相等i3, j3。i3, j3S[3]bP[3]b相等i4, j4。i4, j4S[4]aP[4]d失配。此时 jnext[4]2。主串指针 i 不动模式串从下标 2 开始。i4, j2S[4]aP[2]a相等i5, j3。i5, j3S[5]bP[3]b相等i6, j4。i6, j4S[6]cP[4]d失配。jnext[4]2。i6, j2S[6]cP[2]a失配。jnext[2]0。i6, j0S[6]cP[0]a失配。jnext[0]-1。j-1进入第一个分支i7, j0。继续匹配到 i12, j0 时S[12]bP[0]a失配……之后一直推进到 i13, j0S[13]dP[0]a失配。i14, j0S[14] 超出主串长度循环结束j ! len(p)返回 -1。在这个模拟里你会看到主串指针一路从 0 走到 14没有一步回头。模式串的调整完全靠 next 数组完成。这就是 KMP 最核心的直观认识。匹配阶段的主串指针不回退带来的直接收益是当主串特别长时不会因为模式串的开头反复出现在主串的不同位置而反复扫描同一段主串字符。这一点在基因序列比对、日志关键字提取这类场景中格外重要——这些场景下主串常常以千万甚至亿为单位任何一点重复扫描都是实打实的性能损失。5. 从刷题到工程几个高频场景的实战应用与变种字符串匹配不只是找一个子串这么简单。KMP 的价值在于它的核心思想——前缀函数的复用——可以迁移到很多相关问题上。我挑几个典型场景展开讲讲这些也是各类算法练习平台上的常客。5.1 统计模式串在主串中出现的次数这个问题在日志分析里很常见。比如你想统计某段代码日志里 ERROR 出现几次。最简单的做法是每次找到一个匹配后主串指针继续往后走统计计数加一。关键在于找到一次匹配后模式串指针下一步怎么处理如果匹配之间允许重叠比如在 aaaa 中找 aa那找到一次后j 不能简单地归零那样会漏掉重叠的匹配。正确做法是让 j next[j]继续匹配。如果你用的是前面定义的 next 数组在 j len(p) 时next[j] 依然有意义它表示 P 自身的最长相等前后缀长度也就是匹配成功后模式串可以滑过去多少字符。这个使用方式意味着 KMP 天然能处理重叠匹配的问题这也是很多人在用 Java 的 indexOf 或 Python 的 str.find 统计出现次数时容易踩的坑——这些内建函数默认不重叠计数。5.2 判断字符串是否由某个循环节重复构成这是个非常经典的 KMP 衍生应用若字符串 S 长度为 L它的 next 数组在末尾的值 next[L]注意这里要计算完整数组包括最后一个字符的下一位记为 k那么当 L % (L - k) 0 时S 的最小循环节长度就是 L - k。这个结论来自前缀函数的一个性质字符串 S 的最小循环节长度等于 L - next[L]前提是 L 能被 L - next[L] 整除。这个判断在压缩存储、周期信号检测、DNA 序列重复片段识别里都有实用价值。我自己就在一次处理传感器时间序列数据时用过它有一段数据周期性明显但周期长度未知用 KMP 的这个性质快速算出了周期值比肉眼挑周期快得多。5.3 KMP 思想在多模式匹配中的延伸你可能听过多模式匹配的 AC 自动机Aho-Corasick Automaton它能在一次扫描中同时匹配多个模式串。AC 自动机本质上就是 KMP 的前缀函数思想从单字符串扩展到 Trie 树上——每个节点都挂一个 fail 指针这个指针的构造逻辑和 next 数组如出一辙。理解了 KMP 的 next再去看 AC 自动机的 fail 指针会发现几乎是一回事。所以在学习路径上KMP 往往不是终点而是通向更高级字符串算法的第一级台阶。你在这里建立起利用模式串自身结构来避免回退的思维模型后面接触后缀数组、Manacher、AC 自动机时会有一种似曾相识的感觉。5.4 结合搜索词场景处理回文子串和长度为3的连续子串问题最近在牛客网上有一类很热的字符串题比如Alice 得到了一个字符串 s她想知道有多少个回文子串或者统计长度为 3 的连续子串的分布。有人会尝试用 KMP 去解决回文子串计数这里我要说清楚一个边界KMP 本身不擅长处理回文问题因为回文判断需要的是中心扩展或 Manacher 这类算法KMP 是基于前缀匹配的。但是长度为 3 的连续子串计数这类问题本质上是把每个长度为 3 的窗口当作一个模式串去主串中统计出现次数这种多模式场景恰恰可以用 KMP 的变种 AC 自动机也可以暴力预处理所有窗口后配合哈希做。理解 KMP 能帮你建立一种思维任何在主串里反复查找某种固定结构的问题都可以先考虑模式串的结构能否被预处理。6. 工程实战中的避坑清单这些错误我几乎都犯过KMP 的代码虽然短但真正写起来、改起来坑一点都不少。我把这些年自己踩过的和帮别人排查过的典型问题整理成一份清单。6.1 死循环忘记处理 j -1 的分支这是最常见的错误。在匹配循环里如果失配并且 j next[j] 一路退到 -1但你的代码没有处理 j -1 的情况那么下一步访问 P[j] 就直接越界或者循环条件 j len(p) 永远成立形成死循环。我见过不少人把 next 数组定义成减一版之后在匹配时写j next[j] 1而不是j next[j]这也是同源问题。建议在所有用到 next 的代码路径上先单独写好 j -1 的处理再写匹配逻辑。6.2 边界模式串长度为 0 或 1 时的特殊处理当模式串长度 n 1 时next 数组只有 [-1]。匹配时如果失配j 直接跳到 -1进入主串前进分支。但如果模式串为空串很多实现会直接越界。工程上建议在一开始就判断如果 len(p) 0直接返回 0 或按照业务约定处理。有些人在 LeetCode 上把空模式串的返回结果猜成 -1其实按字符串匹配惯例空串匹配任何位置通常返回 0。6.3 next 数组定义混用前面提过不同教材、不同语言的实现里 next 数组的定义有差异。有的是失配后 j 去往的位置有的是最长相等前后缀长度有的整体偏移了一位。如果你直接拿来别人的 next 数组配合自己的匹配逻辑很可能出现下标越界或匹配结果不正确。强制建议整个项目里只认一种定义并且写注释说明清楚。6.4 计算 next 时误用原字符串越界构建 next 的过程中核心逻辑是if p[j] p[k]这里的 j 和 k 都在合理范围内不会越界因为它们都被 while 条件约束。但如果你用 for 循环从 0 到 n-1 遍历并且循环体内直接取 p[j1] 而不做判断就会在最后一次迭代时越界。稳妥写法是像我上面示例里那样用while j n - 1保证 p[j1] 有定义。6.5 处理 Unicode 或中文字符串时的字节偏移如果你在 Python 里用 KMP 处理中文字符串要注意 len() 返回的是字符数而不是字节数这本身没问题但如果你在 Java 中用 char 数组处理 UTF-16 编码的字符串遇到 emoji 这类代理对字符时KMP 会在双字节字符中间失配导致匹配结果错误。这类场景下最简单的做法是把字符串先转成码点数组或者直接用语言自带的字符串匹配能力只在真正需要手写 KMP 的场景里写 KMP。6.6 性能陷阱提前退出与大数据量下的空间优化KMP 的 next 数组是一个长度为 n 的整数数组在模式串很短时可以忽略不计。但如果你在一个内存受限的环境里匹配一个超长模式串比如 n 达到百万级那 next 数组占用的内存就不容忽视了。这时可以改成只保留必要跳转信息的压缩版本或者改用双向匹配算法。不过绝大多数场景下n 不会特别大没必要过度设计。7. 从一道实际题目看 KMP 的完整解题流程我这里用一个稍微复杂一点的例子帮你把前面所有内容串起来。题目是给定一个文本 T 和一个模式串 P要求输出 P 在 T 中所有出现的位置可能重叠。这个题如果放在牛客网上输入输出格式一般是这样第一行是模式串第二行是文本。你需要输出所有匹配的起始下标每个一行。我直接给出一个完整的 Python 实现def build_next(p): n len(p) nxt [-1] * n j, k 0, -1 while j n - 1: if k -1 or p[j] p[k]: j 1 k 1 nxt[j] k else: k nxt[k] return nxt def kmp_find_all(t, p): nxt build_next(p) res [] i j 0 while i len(t): if j -1 or t[i] p[j]: i 1 j 1 if j len(p): res.append(i - j) j nxt[j - 1] if j 0 else 0 else: j nxt[j] return res t abababab p abab print(kmp_find_all(t, p)) # [0, 2, 4]这段代码我特别说明一下匹配成功后的处理当 j 走到模式串末尾说明找到一个匹配起始下标是 i - j。然后为了继续找下一个可能重叠的匹配j 应该回退到 next[len(p)-1] 的位置——也就是模式串自身的最长相等前后缀对应位置。这样abab 在 abababab 中就能正确找到下标 0、2、4 三处。如果你把这处写成 j 0那就会漏掉重叠的匹配只能得到 [0, 4]。这个细节我在面试别人的时候经常拿来当加分项确实很多候选人会在这里栽跟头。8. 复杂度分析的直观理解与几种匹配算法对比很多人记住了 KMP 的时间复杂度是 O(mn)但对为什么是加法而不是乘法缺少直观感受。我用一句话说明白匹配阶段主串指针 i 最多从 0 走到 m每一步要么匹配成功让 i 和 j 同时前进要么失配让 j 跳转。q 的跳转次数和 i 的前进次数是相互制约的——j 每跳转一次都是由一次失配触发的而每次失配之前必然有一次 i 的前进。所以 i 的前进次数是 mj 的跳转次数不超过 2m 量级总体线性。构建 next 的阶段j 指针最多前进 n 次k 的跳转次数也受到 j 前进次数的约束同样线性。用一个表格来对比常见字符串匹配算法的定位可能更直观算法最坏时间复杂度主串指针是否回退需要额外预处理适用场景暴力匹配O(m×n)是无文本和模式串都很短KMPO(mn)否是主串特别长模式串较短且可能重复出现BM 算法最坏 O(m×n)平均亚线性否是模式串较长字符集较大Rabin-Karp平均 O(mn)最坏 O(m×n)是哈希预处理多模式串匹配或等长子串查找这里多说一句 BM 算法它在实际文本编辑器里往往比 KMP 表现更好因为它利用的是从右往左比较的坏字符规则和好后缀规则大部分情况下能跳过更多字符。但 BM 的最坏复杂度仍然是 O(m×n)所以如果你需要严格的时间复杂度保证KMP 反而是更稳的选择。KMP 的价值从来不是最快的匹配算法而是在保证线性时间的前提下思想极具普适性。9. 自我检测与进阶练习如何判断你真的掌握了 KMP最后这部分我设计了一组自测问题。如果你能不看代码完整回答出下面的问题说明你对 KMP 的理解已经到了能够灵活运用的程度。为什么 next[j] 的长度取最长相等前后缀而不是任意一个相等前后缀如果取短了会发生什么在构建 next 的过程中k next[k] 这一步到底在做什么它和匹配失配时的跳转是同一个逻辑吗如果要统计重叠出现的次数匹配成功后 j 应该怎么处理如果统计非重叠次数j 又该怎么处理模式串 aaaab 的 next 数组是什么你能手算一遍并验证吗有一个字符串 S如何用 KMP 判断它是否是某个子串的幂即 S 能被某个更短的字符串重复若干次拼成这几道题都能在正文里找到答案线索但只看不练肯定不行。我的建议是挑一个模式串手工模拟一遍完整的构建 next 和匹配过程再把代码实现一遍最后拿几个边界用例比如空串、单字符串、全相同字符去测试。整个过程一小时左右远比看十篇教程有效。从我个人带新人的经验来看KMP 这个算法的高频错误里有一半以上出在对 next 数组定义的不统一上。如果你能在项目初始阶段就定好规范并给自己写一份注释文档后面不管是调 bug 还是扩展功能都会省心很多。把这套思路理解透再看 AC 自动机、后缀数组这些更复杂的东西你会觉得那不过是 KMP 的又一次变装而已。