如果你在洛谷刷字符串专题P3375 基本是绕不开的一道模板题。它就是让你实现 KMP 字符串匹配算法给一个文本串和一个模式串输出模式串在文本串里所有出现位置然后再输出模式串每个前缀的 next 数组。题目本身不长但想一次 AC 还真没那么容易尤其是被 next 数组的多种定义坑过的人绝对不止我一个。这道题适合刚学完 KMP、想在 OJ 上验证模板的选手也适合已经会背模板但对“为什么这样回退”还一知半解的人。我会把前缀函数的推导、匹配循环的每一步、下标换算这些细节全部拆开讲一遍再给一份可以直接抄的 AC 代码。写的过程中我尽量沿用做题时的思路来组织你照着理一遍之后不管换哪个平台、换哪道字符串题心里都有底。1. 先读懂题目P3375 到底在考什么1.1 原题要求拆解P3375 的题意用大白话说就是给你两个字符串 s1 和 s2s2 是模式串你要在 s1 里找出 s2 出现的所有位置。位置编号从 1 开始算输出时每个位置占一行。输出完位置之后还要单独输出一行内容是 s2 每个前缀的 next 值这里的 next[i] 表示 s2 从第 1 个字符到第 i 个字符这个子串中最长相等前后缀的长度。注意这个定义。next[1] 固定是 0因为单个字符组成的字符串它的“真前缀”和“真后缀”都是空串长度只能算 0。这个定义其实就是算法导论里说的“前缀函数 pi”很多人也直接叫 border 数组。题目里叫 next但千万别和某些教材里那个“失配后跳到哪”的 next 数组搞混否则输出会完全不对。举个例子s2 ABA它的三个前缀分别是 A、AB、ABA。A 的 next 是 0AB 的 next 是 0A 和 B 不相等ABA 的 next 是 1前缀 A 等于后缀 A。所以这一行输出 0 0 1。如果你的代码输出的是别的多半是 next 定义理解偏了。数据范围方面s1 和 s2 的长度都能到 10^6 级别所以 O(n*m) 的朴素匹配是肯定过不去的。题目虽然没说得很夸张但 1 秒左右的时间限制下必须用线性算法这就是 KMP 出场的原因。1.2 朴素匹配为什么不行朴素匹配的思路很简单从文本串的每一个位置开始挨个和模式串比较一旦遇到不匹配就整体右移一位重新从模式串开头比。最坏情况下文本串是 AAAA...AB模式串是 AAA...AB每次都要比到最后一位才发现失败然后只移动一格总复杂度 O(n*m)。n 和 m 都是 10^6 的时候10^12 次比较跑完不知道要等到什么时候。朴素匹配真正浪费的地方在于它把已经比过的信息全扔了。文本串里某个子串明明已经和模式串的前缀匹配了一长段只是最后一个字符不匹配朴素算法还是固执地从模式串第 0 位重新开始。KMP 的聪明之处就是记住这一段“已经匹配的前缀”里后半部分有没有恰好和某个更短前缀重合的部分失配时直接把模式串挪到那个重合的位置继续比从而保证文本串指针永不回退。一句话总结KMP 让模式串在失配时“有记忆地滑动”而不是“无脑整体右移”。这个“记忆”就存在 next 数组里。2. KMP 的核心前缀函数与 next 数组2.1 什么是 border什么是前缀函数border 是字符串领域一个很顺口的叫法。一个字符串的 border 就是它“既是前缀又是后缀”的真子串。注意“真”字指的是不能等于字符串自己。比如 ABCAB 的 border 是 AB长度为 2再长就没有了AAAA 的 border 有 AAA、AA、A最长的是长度为 3 的那个。最长 border 的长度就是前缀函数的值。为什么 KMP 需要 border因为当模式串匹配到一半失配时我们已经确认了文本串中当前这一段与模式串的某个前缀完全一致。假设这个前缀长度为 j那它的最长 border 长度是 pi[j-1]。既然这个前缀的后 pi[j-1] 个字符和它的前 pi[j-1] 个字符一样而文本串里对应的后 pi[j-1] 个字符也已经被验证过了我们就可以直接把模式串的指针回退到 pi[j-1]拿文本串当前字符继续和模式串的第 pi[j-1] 个字符比较。这个操作本质上就是在“安全地滑动模式串”。打个比方你手里有一截绳子上面有一段连续的花纹刚好对上了墙上的花纹。某个位置对不上了你不会把绳子完全拉回起点重新对齐而是先看看已经对上这段花纹的尾部是否和绳子开头的某段花纹相同。如果相同就利用这段相同花纹把绳子“平移”到尽量靠后的位置继续对齐。KMP 就是这个过程的自动化版本。2.2 前缀函数的计算逻辑与手算演示计算 pi 数组的代码非常短网上到处都有但很多人是背着写的。我建议从递推的角度理解而不是死记。假设我们已经知道了 pi[0] 到 pi[i-1] 的所有值现在要求 pi[i]。设 j pi[i-1]意思是前 i 个字符下标 0 到 i-1的最长 border 长度为 j。我们想看看把当前字符 p[i] 拼上去之后这个最长 border 能不能继续延长。如果 p[i] 恰好等于 p[j]那太好了新的最长 border 长度就是 j1pi[i] j1。如果不等我们就需要“退而求其次”找前 i 个字符的次长 border再看 p[i] 能不能接上。次长 border 的长度是多少其实就是 pi[j-1]。因为最长 border 的长度是 j那么它自己的最长 border 就是整个子串的次长 border。这是一个嵌套递推的关系所以代码里就是一个 while 循环不断回退 j pi[j-1]直到找到某个 j 满足 p[i] p[j]或者 j 已经退到 0。用 ABABAC 手算一遍。pi[0] 0单个字符没有真 border。i1p[1]Bjpi[0]0p[1] 不等于 p[0]A所以 pi[1]0。i2p[2]Ajpi[1]0p[2]p[0]pi[2]1。i3p[3]Bjpi[2]1p[3]p[1]pi[3]2。i4p[4]Ajpi[3]2p[4]p[2]pi[4]3。i5p[5]Cjpi[4]3p[5] 不等于 p[3]B于是 jpi[2]1p[5] 不等于 p[1]Bjpi[0]0p[5] 不等于 p[0]Api[5]0。最终 pi 数组是 0 0 1 2 3 0。注意 while 循环里必须写 j 0 这个条件。因为当 j 回退到 0 时pi[-1] 不存在再继续回退就会越界或者死循环。这是新手写 KMP 最容易炸的地方后面我会单独列一节说。2.3 三种 next 定义的血泪史我学 KMP 时最大的障碍不是算法本身而是 next 数组的一堆变种定义。不同教材、不同博客、不同 OJ 题目next 的含义可能都不一样直接套模板容易错得莫名其妙。常见的至少有三种。第一种是洛谷 P3375 要的 pi 数组也就是每个前缀的最长 border 长度下标从 0 开始pi[0] 恒为 0。第二种是某些数据结构教材里的 next 数组用 1-based 下标next[i] 表示前 i 个字符组成的前缀中最长真前后缀长度加 1或者说模式串第 i 位失配时指针应该跳到第几位。第三种是更进阶的 nextval在 next 基础上做了优化把重复字符导致的无效回退给压缩掉了。很多老博客喜欢用 1-based 的写法循环里 next[1] 0i 从 2 开始。如果你拿那套模板直接套 P3375输出 border 长度那一步就会差一个 1或者干脆全部错位。我给你的建议是不要来回切换定义认准 pi 数组这一种其余的定义当知识了解就行。洛谷这套题输出的是 border 长度用 pi 数组最自然。下面这个表可以把三种定义对比清楚方便你遇到其他资料时快速转译名称下标起点pi[i] 的含义与 pi 数组的关系前缀函数 pi0前 i1 个字符的最长 border 长度基准定义教材 next1第 i1 位失配时跳转的位置next[i] pi[i-1] 1教材 nextval1进一步优化后的跳转位置在 next 基础上压缩表格里“教材”指国内常见数据结构教材。如果你看到某个题解里的 next 输出比 pi 大 1别惊讶它很可能用了第二种定义。3. 匹配阶段的完整实现3.1 匹配循环的逐句拆解算完 pi 数组匹配阶段的代码和构建 pi 数组的代码长得几乎一模一样。这不是巧合你可以把匹配过程理解成文本串 s 是“新来的字符”模式串 p 是“待构建的前缀”我们不停地用 s 的每一个字符去扩展当前匹配的“隐式前缀”长度 j。一旦 j 达到 m就说明找到了一个完整匹配。具体地j 初始为 0表示当前已经匹配了模式串的前 0 个字符。遍历文本串的每个字符 s[i]先进入一个 while 循环只要 j 大于 0 并且 s[i] 不等于 p[j]就把 j 回退到 pi[j-1]。这一步就是在利用已匹配部分的信息跳过不可能成功的对齐位置。回退到 0 或者 p[j] 等于 s[i] 之后如果 s[i] 等于 p[j]j 就加 1表示又匹配上一个字符。当 j 增长到 m 时当前文本串中从 i-m1 到 i 这个长度为 m 的窗口正好就是模式串。这时记录答案位置是 i-m2因为我们用的是 0-based 下标而题目要求 1-based 位置转换之后要加 2 而不是加 1这个公式容易搞错我待会专门解释。记录完答案后j 不能直接归零而要回退到 pi[m-1]因为匹配成功的这一段后面可能紧跟着另一个匹配比如文本串 AAAA 和模式串 AA位置 1 记录完紧接着位置 2 也是合法匹配j 归零就会漏掉。这里有同学会担心如果 j 已经等于 mwhile 循环里比较 s[i] 和 p[j] 时访问 p[j] 会不会越界不会因为我们在 j 等于 m 的当下就立刻记录答案并回退了下次再进入下一轮循环时j 已经变成 pi[m-1]肯定小于 m。只要你的回退代码写在 jm 判断的同一轮里并且正确执行就不会访问到 p[m]。3.2 两份可直接 AC 的代码先给一份基于字符数组的写法性能最稳适合大输入、时限紧的场景#include bits/stdc.h using namespace std; const int N 1000005; char s[N], p[N]; int pi[N]; int main() { scanf(%s, s); scanf(%s, p); int n strlen(s), m strlen(p); // 求模式串每个前缀的最长 border 长度 for (int i 1; i m; i) { int j pi[i - 1]; while (j 0 p[i] ! p[j]) j pi[j - 1]; if (p[i] p[j]) j; pi[i] j; } // 用 pi 数组在文本串里匹配模式串 int j 0; for (int i 0; i n; i) { while (j 0 s[i] ! p[j]) j pi[j - 1]; if (s[i] p[j]) j; if (j m) { printf(%d\n, i - m 2); j pi[j - 1]; } } // 输出前缀函数 for (int i 0; i m; i) { printf(%d , pi[i]); } printf(\n); return 0; }如果你更习惯用 string可以写下面这版。注意必须手动关闭 C 标准输入输出流的同步否则数据量一大就很容易超时#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); string s, p; cin s p; int n s.size(), m p.size(); vectorint pi(m); for (int i 1; i m; i) { int j pi[i - 1]; while (j 0 p[i] ! p[j]) j pi[j - 1]; if (p[i] p[j]) j; pi[i] j; } int j 0; for (int i 0; i n; i) { while (j 0 s[i] ! p[j]) j pi[j - 1]; if (s[i] p[j]) j; if (j m) { cout i - m 2 \n; j pi[j - 1]; } } for (int i 0; i m; i) cout pi[i] ; cout \n; return 0; }两份代码都只用了一次循环求 pi一次循环匹配时间复杂度 O(nm)空间复杂度 O(m)。提交时语言选 C17 或 C14 都行。3.3 输出位置公式 i - m 2 是怎么来的这个公式是 WA 高发区我单独拿出来讲。字符串用 0-based 下标时如果当前匹配到了模式串最后一个字符 p[m-1]且它对应文本串的 s[i]那么这次匹配覆盖的文本串范围是 s[i-m1] 到 s[i]模式串第一个字符在文本串中的下标是 i-m1。题目要求位置从 1 开始编号所以真实输出应该是下标加 1也就是 i-m11 i-m2。很多时候会有人写成 i-m1那是忘了做从 0 到 1 的偏移。反过来如果你把字符串读进下标从 1 开始的 char 数组匹配时就得用 i-m1。总之先搞清楚自己的字符串是从 0 开始还是从 1 开始每次只做一次换算别在代码里到处混着加 1 减 1。验证一下样例s1 ABABABCs2 ABAm3。第一次完整匹配发生在 i2输出 2-321第二次完整匹配发生在 i4输出 4-323。结果正好是样例里的 1 和 3。你把这两次匹配在纸上画一下就知道位置 2 时文本串 ABA 正好对应模式串 ABA位置 3 时从第三个字符开始的 ABA 也匹配所以两个答案都已覆盖。这里要注意位置是从 1 开始计数所以 s[2] 是第三个字符对应位置 3和公式完全吻合。4. 实战中的常见坑与排查4.1 TLE 与读写优化P3375 的 n 和 m 都可能有 10^6如果用了 cin 但不关同步或者循环里每轮都调用 strlen超时几乎是必然的。先说 cin/cout默认情况下 C 的 cin/cout 会和 C 的 stdio 同步保证混用 printf 和 cout 时输出不乱序代价是每次 IO 都要做额外检查慢得很。刷题时养成习惯main 开头写ios::sync_with_stdio(false); cin.tie(nullptr);这两行一写cin 的速度大约能追平 scanf。再说 strlen 的坑。如果你写for (int i 0; i strlen(p); i)每次循环都要重新扫描一遍整个字符串求长度复杂度直接变成 O(m^2)。在 10^6 级别的数据上这就是慢到怀疑人生的根源。正确做法是提前把长度存到变量 n、m 里。这个习惯对任何字符串题都适用不只是 KMP。另外洛谷对这道题的时间限制并不宽裕如果你的代码用了 vector 并且反复扩容或者输出时用了 endl 而不是 \n也可能卡在超时边缘。endl 会强制刷新缓冲区大量输出时效率极低字符串题里一律用 \n。4.2 数组越界与死循环KMP 代码里最经典的死循环出现在 while 回退部分。很多人写的时候漏掉j 0这个条件写成while (p[i] ! p[j]) j pi[j - 1];当 j 已经是 0pi[j-1] 就是 pi[-1]下标越界。在某些编译环境下可能不会立刻报错而是读到一个随机值程序直接行为失控。即使 C 的越界读碰巧没崩逻辑上也会停不下来。正确的写法是while (j 0 p[i] ! p[j]) j pi[j - 1];。这个条件顺序不能反j 0必须在前因为 C 的是短路求值j 等于 0 时根本不会去访问 p[j]也就不会越界。构建 pi 和匹配阶段的两处 while 都要这样写只改一处、漏掉另一处的情况也很常见排查时要两个循环都检查。匹配阶段还有一个隐藏越界点如果 j 已经等于 m再去比较s[i] p[j]就越界了。我前面给的代码里因为 j 每次到达 m 后立刻输出并回退到 pi[m-1]所以进入下一次迭代时 j m不会踩到 p[m]。但如果你调整了代码顺序比如把回退写到下一次循环开头就比较危险。保险的写法是在比较前加一句if (j m) j pi[j-1];或者直接判断if (j m s[i] p[j])。对于新手我更建议先把模板固定成上面那两份别随意改动执行顺序。4.3 WA 的几类典型原因WA 的原因比 TLE 更隐蔽常见的有三种。第一种是 next 定义混乱把 pi 数组和教材 next 数组搞混输出差 1。如果你是在别的博客上找的模板先看它里面 next[i] 的含义到底是不是“最长 border 长度”不是的话必须转成 pi 再输出。第二种是下标混乱0-based 和 1-based 混用导致出现位置偏 1。解决方法是全程统一 0-based只在输出位置时加一次偏移 2。第三种是匹配成功后 j 直接归零而不是回退到 pi[m-1]导致重叠匹配丢失。比如文本串 ABABA模式串 ABA正确输出应该是 1 和 3j 归零的写法只能输出 1。还有一个小细节输出 pi 数组时每个数后面带一个空格最后多一个空格洛谷一般不算错评测器会忽略行末空格。如果你实在担心可以写成if (i m-1) printf(%d\n, pi[i]); else printf(%d , pi[i]);但这不是必须的。我提交过很多次行尾多一个空格没有 WA 过。下面把刚才提到的坑整理成速查表排查时对照着看现象可能原因解决办法超时cin 未关同步 / 循环内调 strlen / endl关同步预存长度用 \n越界或死循环while 少了 j0 条件补条件保持短路求值顺序位置输出偏 10-based 下标只加了 1用 i-m2漏掉重叠匹配匹配成功后 j0改为 jpi[j-1]第二行输出错next 定义混用统一用 pi 数组语义4.4 从模板题延伸出去的内容P3375 虽然是模板题但它背后的 KMP 绝不仅限于输出匹配位置。AC 之后我建议你顺手试几个延伸方向能帮你把这道题的理解再加深一层。一是求最小循环节。如果一个字符串存在某个循环节那么它的长度就是 n - pi[n-1]。这个结论看起来像魔法推导思路其实是最长 border 的长度意味着字符串可以写成“前缀后缀”重叠的形式重叠部分越长剩余部分越短当剩余部分能整除总长度时就构成了循环节。经典题目比如洛谷 P4391就是在 KMP 基础上套用这个结论。二是用 KMP 做字符串周期相关的计数题比如问一个字符串的所有周期或者统计模式串在文本串中的不重叠出现次数这类题只需要微调匹配成功后的回退位置或者在回退时加上长度限制。三是对比学习 Z 算法。Z 算法和 KMP 在思路上有很多相通之处都是利用已计算部分的信息避免重复比较但一个维护的是“文本串匹配前缀长度”一个维护的是“每个后缀和整个字符串的最长公共前缀”。两个都学了以后你会对线性字符串匹配有更整体的认识。从更高的视角看KMP 的 pi 数组本质上是给模式串构建了一棵 fail 树pi[i-1] 就是 i 的父节点。很多字符串处理里的高级算法都在这棵树上做文章比如 AC 自动机就是把 KMP 的思想从单模式串扩展到了多模式串。你现在在 P3375 上多花的一点时间后面都会被连本带利地还回来。最后分享一个我自己刷题时的小习惯准备一份“干净”的 KMP 模板不写题目相关的任何输出逻辑只包含读入字符串、求 pi、匹配并返回所有位置这三个核心部分。每次遇到需要 KMP 的题先把这个模板贴进去再往匹配成功的回调里填具体需求。这套模板我用了很久基本没有改过。刚做完 P3375 的人不妨现在就整理一份属于自己的版本以后刷题能省下很多重复调试的时间。