在 Acwing 算法基础课里831.KMP字符串 这道题的位置非常有意思——它前面是各种大名鼎鼎的数据结构后面就要进入图论而它自己看起来只是在一个长串里找模式串出现的所有位置。但恰恰是这道题让很多人第一次体会到什么叫算法设计也第一次在模板代码前卡住next数组到底在存什么为什么匹配失败要 j ne[j]为什么输出下标是 i - n 而不是 i - n 1如果你正准备机试、考研复试或者刚开始刷 Acwing那这篇文章就是为你准备的。我会从暴力匹配开始把 KMP 的完整推导思路、代码逐行拆解、Acwing 831 的题目细节、以及我三年里反复踩过的坑全部展开。KMP 不是一个需要背模板的算法只要把最长相等前后缀这几个字搞透代码几乎是顺理成章写出来的。1. 暴力匹配能过多少题先把朴素写法写对1.1 一个最朴素的 O(n*m) 写法在讨论 KMP 之前先把暴力匹配写对。假设主串是s长度为m模式串是p长度为n要输出p在s中所有出现位置的起始下标用 0 作为基准for (int i 0; i n m; i) { bool flag true; for (int j 0; j n; j) { if (s[i j] ! p[j]) { flag false; break; } } if (flag) printf(%d , i); }外层循环枚举主串的每一个可能起点内层循环逐个字符比对。这段代码的逻辑没有任何问题做题时如果时间充裕小数据范围也能 AC。但它的时间复杂度是 O(n*m)当n是 10^5、m是 10^6 级别时跑一次就要 10^11 次操作完全不可接受。1.2 暴力慢的本质已经比过的信息被丢掉了暴力匹配到底慢在哪里核心问题不是比了很多次而是每次失配后主串指针 i 要回退之前已经比对过的字符信息被全部丢弃。举个最极端的例子s aaaaaaaaaaaaaaaaabp aaab暴力匹配会把前面那几十个a反复比对很多遍但实际上每个字符只需要看一次就够了。真正优质的字符串匹配算法都应该让主串指针只向前走不回头——KMP 就是这类算法的代表。所以 KMP 要解决的问题可以精确描述成当主串某位与模式串失配时已知主串当前位置之前的 j 个字符已经匹配上了那么模式串的指针应该回退到哪个位置才能不重不漏地继续匹配2. KMP怎么省时间失配时不回退主串2.1 next数组在记录什么最长相等前后缀KMP 的答案是给模式串预处理一个next数组。在 Acwing 的 1-indexed 写法里ne[i]表示模式串前 i 个字符组成的子串中最长的相等的真前缀和真后缀的长度。举个例子p abcabx看p[1..5] abcab前缀集合a,ab,abc,abca后缀集合b,ab,cab,bcab交集{ab}最长长度是 2所以ne[5] 2。注意这个长度不能等于 i 本身也就是说整个子串不能算作它自己的前后缀否则ne[i]永远是 i没有任何意义。真前后缀这个概念是整个 KMP 的基石忘了什么都不能忘这个定义。用大白话理解ne[j]告诉你当模式串已经成功匹配了 j 个字符准备匹配第 j1 个字符时如果第 j1 位失配j 至少可以退回到 ne[j]因为模式串开头 ne[j] 个字符和刚刚匹配完的那段内容的最后 ne[j] 个字符长得一模一样已经不需要重新比较了。2.2 失配回退的逻辑为什么 j ne[j] 是安全的假设现在匹配到主串的i位置模式串的j位置也就是s[i]与p[j1]正在比较。如果失配意味着主串s[i-j1 .. i]这一段已经和p[1..j]完全相等。此时我们想知道模式串能不能只回退一部分而不是退回起点从头再来回头看ne[j]。因为p[1..j]的最长相等前后缀长度是ne[j]所以p[1..ne[j]] p[j-ne[j]1 .. j]。而p[j-ne[j]1 .. j]又等于主串s[i-ne[j]1 .. i]因为整段都匹配上了。因此主串当前位置之前 ne[j] 个字符恰好等于模式串的前 ne[j] 个字符这一部分不需要再比对直接把模式串指针从 j 回退到ne[j]然后用主串当前位置继续和p[ne[j]1]比较即可。这个过程很像写文章时的局部修改已经写好的一大段里结尾恰好和开头重复了几句那这几句就不用重写直接从重复部分后面接着改。KMP 省掉的时间正是省在这些不用重新比较的字符上。主串指针 i 始终保持不回退整个匹配过程只关心模式串指针 j 如何变化——这是 KMP 最核心的设计思想也是它复杂度的来源。2.3 用 P aba、S abababa 把匹配过程推一遍光看文字容易晕拿具体例子推一遍。设p abas abababa都是 1-indexed 存储。先直接给出ne数组ne[1] 0,ne[2] 0,ne[3] 1。这三个值的含义分别是a没有真前后缀ab没有相等的前后缀aba的a和a相等长度为 1。匹配过程如下表is[i]比较j处理后说明1as[1] p[1]1首个字符匹配2bs[2] p[2]2继续匹配3as[3] p[3]3 → 1j n输出位置 i - n 0j 回退到 ne[3] 14bs[4] p[2]2直接从 p[2] 开始比5as[5] p[3]3 → 1匹配成功输出 5 - 3 2j 回退到 16bs[6] p[2]2继续7as[7] p[3]3 → 1匹配成功输出 7 - 3 4j 回退到 1最终输出0 2 4手工检查abababa中aba出现的位置确实分别是 0、2、4。注意第 4 步之后j 从 1 变成 2只比较了p[2]这一个字符如果暴力匹配主串指针要回退到 i2 重新比三个字符。这就是 KMP 省时间的直观体现。3. next数组是怎么求出来的模式串和自己匹配3.1 递推思想已知 ne[1..i-1] 求 ne[i]next数组是整个 KMP 的预处理环节它的求法其实和匹配过程是同一个套路——模式串自己在匹配自己。假设我们已经求出了ne[1]到ne[i-1]现在要求ne[i]。先看ne[i-1]它告诉我们p[1..ne[i-1]]等于p[i-ne[i-1] .. i-1]也就是说前ne[i-1]个字符已经和紧挨着 i 的前一段字符相等。接下来只要比较p[ne[i-1]1]与p[i]如果相等说明最长相等前后缀可以延长一个字符ne[i] ne[i-1] 1。如果不相等就需要找一个更短的、依然是p[1..i-1]后缀的前缀。这个更短的候选长度正好是ne[ne[i-1]]。因为p[1..ne[i-1]]这个子串的内部也存在着前缀等于后缀的结构而这个结构的长度就是递归下去查找ne数组的结果。这就是为什么构建ne时要用while (j p[i] ! p[j1]) j ne[j];不断往更短的候选回退。用p aaab演示一个需要多次回退的例子ne[1] 0i 2p[2] a与p[1] a相等j 1所以ne[2] 1i 3p[3] a与p[2] a相等j 2所以ne[3] 2i 4p[4] b与p[3] a不等j ne[2] 1继续比较p[4]与p[2] a还是不等再j ne[1] 0跳出循环由于p[4] ! p[1]j保持 0所以ne[4] 0这个过程看起来复杂但写进代码只有四行原因就是j ne[j]这个回退操作恰好无缝地嵌在了循环里。3.2 1-indexed 模板代码的逐行拆解Acwing 课程里的模板采用 1-indexed代码是这样for (int i 2, j 0; i n; i) { while (j p[i] ! p[j 1]) j ne[j]; if (p[i] p[j 1]) j; ne[i] j; }逐行拆解i从 2 开始因为ne[1]已知等于 0一个字符没有真前后缀。进入循环时j保持的是上一轮结束后的值也就是ne[i-1]。这是这个模板的一个特点j没有在每轮重新读取ne[i-1]而是由上一轮直接带过来效果完全一样。while循环的目的是持续回退到最长的可行前缀。条件j p[i] ! p[j1]有两个作用一是当j 0时防止访问p[j1]越界二是当字符不相等时回退到更短的候选。如果p[i] p[j1]说明这个前缀可以扩展j。ne[i] j把最终结果存进数组。和匹配过程对比可以发现两段代码结构一模一样都是先循环回退再尝试匹配最后判断长度。区别只在于求ne时比较的是p[i]与p[j1]匹配时比较的是s[i]与p[j1]。理解这一点整个 KMP 就串起来了。3.3 0-indexed 写法LeetCode风格对比很多读者最早接触 KMP 是在 LeetCode 上那里普遍使用 0-indexed 的写法vectorint buildNext(string p) { int n p.size(); vectorint next(n, 0); for (int i 1, j 0; i n; i) { while (j 0 p[i] ! p[j]) j next[j - 1]; if (p[i] p[j]) j; next[i] j; } return next; }0-indexed 的next[i]表示p[0..i]这个子串的最长相等前后缀长度。注意这里的回退写法变成了j next[j - 1]比较对象也从p[j 1]变成了p[j]原因在于下标基准不同。两种写法等价但我建议你在 Acwing 刷题时统一用 1-indexed 模板不要混着背否则非常容易在输出下标时出错。下面是核心差异对比表对比项1-indexedAcwing风格0-indexedLeetCode风格ne[i] 含义p[1..i] 的最长相等前后缀p[0..i] 的最长相等前后缀构建循环起始i 2i 1当前比较字符p[i] 与 p[j1]p[i] 与 p[j]失配回退j ne[j]j next[j - 1]匹配成功输出i - ni - n 14. Acwing 831 实战从题目输入到完整AC代码4.1 题目里的坑输出下标从0开始先看 Acwing 831 的原题要求。输入为第一行整数 N表示模板串 P 的长度第二行字符串 P第三行整数 M表示主串 S 的长度第四行字符串 S。P 在 S 中多次出现要求输出所有出现位置的起始下标下标从 0 开始计数。题目本身不复杂但有一个非常容易踩的坑存储是 1-indexed输出却是 0-indexed。当j n表示匹配成功时匹配区间为s[i-n1 .. i]。这个区间的起始位置按 1-indexed 算是i - n 1换算成题目要求的 0-indexed 就要再减 1变成i - n。很多第一次写 KMP 的人在这里会惯性地写成i - n 1受 0-indexed 的 LeetCode 模板影响结果整个输出整体向右错一位拿到 WA 后还百思不得其解。这个细节我下面会专门展开讲这里先记住结论。4.2 完整代码与注释#include iostream using namespace std; const int N 100010, M 1000010; int n, m; char p[N], s[M]; int ne[N]; int main() { cin n p 1 m s 1; // 求 next 数组 for (int i 2, j 0; i n; i) { while (j p[i] ! p[j 1]) j ne[j]; if (p[i] p[j 1]) j; ne[i] j; } // KMP 匹配 for (int i 1, j 0; i m; i) { while (j s[i] ! p[j 1]) j ne[j]; if (s[i] p[j 1]) j; if (j n) { printf(%d , i - n); j ne[j]; } } return 0; }注意两个数组大小的细节N开的是100010而不是100000M开的是1000010而不是1000000因为字符串从下标 1 开始存储最多用到p[N]和s[M]所以要各多留一个位置。这是很典型的Acwing 模板式写法宁愿多开一点绝不踩越界。读入部分cin n p 1 m s 1的意思是读入 n、然后从p[1]开始存 P 字符串、再读入 m、从s[1]开始存 S 字符串。p 1是 char 数组的指针偏移写法等价于把字符串首字符放到p[1]。4.3 提交前的几个检查点用模板 AC 之后建议每次提交前都按这个清单自查一遍数组是否开成全局变量并且大小比题目上界多 1局部大数组会爆栈s[1000010]放在 main 函数内部很可能直接段错误。求ne的循环是不是从i 2开始写错成i 1会额外给ne[1]赋值可能导致后面匹配全部错乱。while条件里是否带了j 不带的话当 j 为 0 时会错误地回退到ne[0]未初始化的值逻辑直接崩掉。匹配成功输出后是否执行了j ne[j]这一步的作用是让模式串能够继续配合主串找下一个重叠匹配漏掉它要么死循环要么漏输出。输出是i - n不是i - n 11-indexed 存储对应的是i - n请默念三遍。5. 我在这道题上反复踩过的坑5.1 输出整体错一位问题出在哪我最初在 Acwing 831 上栽的最大跟头就是输出下标。当时刚从 LeetCode 的 0-indexed 思路转过来匹配成功时下意识写了printf(%d , i - n 1);结果样例全对一提交就 WA。后来对照别人代码才发现Acwing 模板的i是 1-indexed而题目要求输出 0-indexed。i - n 1是 1-indexed 的起始位置要转成 0-indexed 必须再减 1。这个错误非常隐蔽因为它不影响匹配本身只影响输出的一个偏移量。排查方法也很简单拿P aba、S abababa手算一遍预期输出0 2 4如果出来1 3 5那就是这个偏移量的问题。5.2 匹配成功后忘了 j ne[j]漏匹配和死循环另一个高频 bug 是匹配成功之后不写j ne[j]。如果不回退下一次循环j仍然等于n甚至后面还会继续增加超出数组边界结果有两个轻则漏掉后续重叠的匹配重则直接死循环或越界崩溃。典型的重叠匹配例子P aaa、S aaaaa正确输出应该是0 1 2。在 i3 时匹配成功一次如果j不回退i4 时j会变成 4而模式串长度只有 3既不会输出1还会访问p[4]越界。加上j ne[j]后ne[3] 2j 回退到 2然后继续尝试匹配 i4依次输出 1、2。5.3 求 next 的循环里少写了 j 这个判断条件求ne数组的代码中while (j p[i] ! p[j 1])里的j条件很容易被忽略。有人觉得p[j 1]不会越界毕竟数组开得够大就把它省了写成while (p[i] ! p[j 1]) j ne[j];但这样在j 0时会访问p[1]然后无论是否相等都可能把j错误地加回 1导致ne[i]恒不为 0。比如模式串第一个字符就不同时本来应该停留在 0却因为p[i] p[1]而变成 1。这个 bug 对短模式串不明显在长串上排查时很折磨人。记住j为 0 时已经没有可回退的位置直接结束 while这个判断就是干这个的。5.4 数组开小和局部大数组爆栈Acwing 831 的m最大是 10^6 级别很多新手习惯定义局部数组int main() { char s[1000010]; // 局部变量可能爆栈 return 0; }在 Windows 默认 1MB 栈空间的编译器环境下char s[1000010]大约是 1MB再叠加其他局部变量就有崩溃风险在部分平台栈限制更小。更稳妥的做法是把数组定义成全局变量全局区内存远大于栈区而且自动初始化为 0排查越界时也更好定位。这是 C/C 写算法题的基本素养KMP 这种题尤其明显。6. KMP之外的延伸循环节、AC自动机和另一个常用方案6.1 利用 ne[n] 求最小循环节ne数组的价值不只在于匹配本身它还经常被用来求字符串的循环节。结论是如果n % (n - ne[n]) 0那么这个字符串的最小循环节长度就是n - ne[n]否则不存在完整的循环节。证明思路不复杂ne[n]是整个字符串的最长相等前后缀长度n - ne[n]是去掉最长相等后缀后剩下的前缀长度。如果整个字符串能被某个短串完整重复拼接那这个短串长度一定是周期而最短周期正好等于n - ne[n]。举两个例子验证。abcabcabcne[9] 69 - 6 3且9 % 3 0循环节就是abc。abababne[6] 46 - 4 2且6 % 2 0循环节就是ab。但要注意如果余数不为 0比如abababa的ne[7] 57 - 5 2但7 % 2 ! 0所以不能说它有循环节。这个结论在 Acwing 后续很多字符串题里会反复出现值得现在就记住。6.2 KMP思想在AC自动机里的位置KMP 处理的是单模式串匹配。当你有多个模式串要同时匹配时就得用到 AC 自动机Aho-Corasick Automaton。AC 自动机的核心是 trie 树但真正让它能在失配时快速跳转的是每个节点上的fail指针。而这个fail指针的构建逻辑本质上就是把 KMP 的失配回退到最长相等前后缀思想从一维的字符串推广到了 trie 树的多叉结构上。所以理解 KMP 的ne数组等于给 AC 自动机打好了地基。很多人直接上手 AC 自动机觉得晕其实是 KMP 的失配链没有真正吃透。这也是为什么 Acwing 基础课要把 KMP 放在数据结构章节的重要位置。6.3 什么时候我用KMP什么时候用字符串哈希在实际刷题和竞赛中字符串哈希尤其是双哈希也是处理匹配问题的高频方案。它的思路是把每个长度为 n 的子串映射成一个整数然后和模式串的哈希值比较。字符串哈希的优点是代码短、思路简单、支持快速子串查询缺点是存在极小概率的碰撞双哈希基本可忽略而且从算法原理来说它不是确定性算法。我个人在比赛中的选择逻辑是面试或考察算法原理时必用 KMP因为面试官想听的是你的推导和复杂度分析。竞赛中需要大量匹配、或者题目还带有子串哈希查询需求时优先字符串哈希写起来更快。模式串数量很多时直接上 AC 自动机而不是在 KMP 基础上做文章。下面是一个简单的横向对比方案时间复杂度确定性实现难度典型场景暴力匹配O(n*m)是极简小数据/一次性匹配KMPO(nm)是中面试、笔试、单模式串匹配字符串哈希O(nm)否有碰撞风险低竞赛、子串快速查询AC自动机O(nsum(m))是高多模式串同时匹配KMP 虽然代码量只有几十行但它是这些匹配系算法里最重要的基石。我个人的学习建议是先不看代码拿出纸笔把p abcabcx的ne数组从头手推一遍再把s abcabcabcx的匹配过程完整写一遍最后再回来对照代码。这个过程做完之后再去装那些细节就容易很多。另外还有一个小技巧如果你在某道字符串题里不确定匹配逻辑写对没有先构造一个P a的边界输入跑一遍再构造P和S完全相同的输入验证是否输出 0最后构造P在S中密集重叠的输入比如P aa、S aaaa检查是否输出所有位置。走完这三组测试KMP 代码的正确性基本就有保证了。