字符串匹配这关很多人第一次卡住就是在 KMP。S001 这道模板题题目名字一口气写了三样东西前缀函数、KMP 应用、字符串周期。乍一看像是三个要背的板子实际它们是一条线——前缀函数是地基KMP 是同一个数组在匹配场景下的应用字符串周期又是同一个数组在另一个场景里的妙用。理解到这个层面你就不需要再死记硬背了。这篇博文我打算把这套东西全部拆开前缀函数到底在算什么next 数组有好几个版本为什么总有人弄混失配时为什么要跳回pi[j-1]以及字符串周期、循环节、border 三者之间的数学关系。顺带把我自己写模板时踩过的坑、对拍时遇到过的问题一起整理出来。适合刚学 KMP 的选手也适合学完一遍回来查漏补缺的人。废话不多说直接从模板题拆解开始。1. 模板题拆解前缀函数、KMP 与周期是一条线1.1 模板题为什么值得反复写S001 这种模板题题面一般很简单给你一个文本串和一个模式串输出模式串在文本串中出现的所有位置再给你一个字符串求它的最小循环节。很多刚入门的朋友会觉得这种题“太基础了没什么好写”但模板题恰恰是最不能跳过的——因为它考察的不是你会不会某个炫技技巧而是你能不能把 KMP 的核心流程完整、无 bug 地写出来。我见过不少选手平时刷难题的时候思路挺活跃一让他现场默写 KMP 就出问题要么while循环写成if要么失配时跳转少减一个一要么边界越界。这些错误在难题里反而容易被“调试过程”掩盖只有在模板题里才会被无限放大。所以我的建议是S001 这类题不要只写一遍每次比赛前拿出来重写一次直到你不需要思考就能顺畅写完才算真正过了这一关。模板题还有一个价值它给出了一个“标准基线”。你后面学 AC 自动机、后缀数组、Manacher都会遇到和前缀函数类似的跳转思想。如果 KMP 的地基打不牢后面这些内容学起来会因为同一个点反复卡壳。反过来地基稳了后面很多算法其实是“前缀函数的思想换了个壳”。1.2 暴力匹配的瓶颈在哪里在没有 KMP 之前字符串匹配最朴素的做法是枚举文本串的每个位置作为起点然后和模式串逐位比较。每个起点最多比较m次m是模式串长度起点有n-m1个最坏时间复杂度是O(n*m)。这个复杂度在什么时候最难看两个典型的坏例子文本串是aaaaaaaaaaaaaaaaab模式串是aaab你每次匹配到最后一个字符才发现失配然后从下一个位置重新开始。文本串和模式串都是大量相同字符构成比如aaaaa里找aaa虽然能匹配上但你重复比较了大量已经知道是相同的位置。暴力匹配的问题不是“比较字符”本身贵而是它把每次失配当成一次完全失败之前所有比较过的信息全部丢弃。KMP 的出发点是失配时不从头再来而是利用“已经匹配部分”的内部结构把模式串滑动到下一个可能匹配的位置。这个“内部结构”就是前缀函数。打个生活化的比方你在查一本词典找某个词条翻到某一页发现只差一个字母对不上正常人不会翻回第一页重新按字母序一个个找而是会利用已经确认的前几个字母直接跳到词典里对应的区段继续查。KMP 做的就是这件事。2. 前缀函数KMP 的地基2.1 前缀函数的定义与 border 概念前缀函数是一个数组pi对字符串s的每个位置ipi[i]表示s[0..i]的最长真前缀与真后缀相等的长度。注意两个关键字前缀和后缀都必须严格小于当前整个子串长度也就是说pi[i] i1。这个相等的部分叫border。举个例子字符串s aabaaabs[0..3] aaba前缀和后缀相等的部分有a长度为 1所以pi[3] 1。s[0..4] aabaa前缀aa和后缀aa相等所以pi[4] 2。等长的 border 可以有很多个比如aaaaa的每个前缀都有多个 border长度 4、3、2、1 都能取到但pi只记录最长的那个。很多人第一次看定义会懵前缀和后缀要求“真”那pi[n-1]会不会等于n答案是不会因为真前缀和真后缀都不能等于整个子串本身所以pi[n-1]最大也就是n-1。这一点虽然细节但后面理解字符串周期时非常关键——最长 border 长度直接决定了最小循环节的长度。border 这个概念值得多说两句因为它是整个 KMP 的“魂”。border 想表达的是当前这段字符串自己和自己有多像。这种“自身重叠”的性质在失配时给了我们一个安全滑动的距离——已经匹配过的部分中有一段后缀同时也是模式串的前缀那这段就不用重新匹配了。2.2 朴素求法为什么慢增量推导怎么想先看朴素做法对每个位置i枚举所有可能的前缀长度1..i倒着枚举更好逐一比较s[0..l-1]和s[i-l1..i]相等就更新pi[i]。这样做每次比较是O(l)总复杂度接近O(n^3)显然不可用。KMP 的前缀函数用的是增量推导从i-1的结果推出i的结果。核心观察是pi[i]至多等于pi[i-1] 1。为什么因为s[0..i]的任意一个 border如果长度大于pi[i-1]那么它去掉最后一个字符后仍然是s[0..i-1]的 border这个 border 的长度至少是pi[i] - 1与pi[i-1]是最大值矛盾。这个观察给了一个枚举方向从pi[i-1]开始尝试扩展不行就退到更短的 border 再试。更具体地计算pi[i]时的跳转方式是记j pi[i-1]这是s[0..i-1]的最长 border 长度。尝试比较s[i]和s[j]如果相等说明s[0..j]是s[0..i]的一个 borderpi[i] j 1。如果不相等j不能直接减一而是要跳到pi[j-1]。为什么因为s[0..i-1]的所有 border 长度是按“套娃”结构排列的最长 border 的次长 border 就是pi[j-1]。沿着这条链一直退直到找到一个位置能接上s[i]或者j退回 0。这个“套娃”结构我不确定的地方很多人在这里卡很久。用俄罗斯套娃来理解最外面的 border 长度是pi[i-1]把最大的套娃拿出来里面套着的是这个 border 自己的最长 border也就是pi[pi[i-1]-1]。失配时不要一个一个长度试直接把当前最大的套娃丢掉看里面的那个能不能接上s[i]不行再往里面丢一层。2.3 前缀函数模板代码与复杂度vectorint prefix_function(const string s) { int n (int)s.size(); vectorint pi(n, 0); for (int i 1; i n; i) { int j pi[i - 1]; while (j 0 s[i] ! s[j]) { j pi[j - 1]; } if (s[i] s[j]) j; pi[i] j; } return pi; }这个代码放在任何 KMP 相关题目里都是核心引擎。复杂度为什么是O(n)表面上while循环每轮都可能跳好多次感觉不像线性。关键点在于j在整个过程里的变化规律每次for循环内j最多通过j增加 1而在while里跳转时j严格减小。j从 0 开始全程最多增加n-1次所以回退的总次数也不会超过前者的总量均摊下来每个字符的处理时间是O(1)总复杂度就是O(n)。这里有个很容易写错的细节if (s[i] s[j]) j;这一行括号里是s[j]而不是s[i-1]或别的什么。因为经过while之后j表示的是“当前尝试扩展的 border 长度”如果s[i]能接上s[j]说明前缀s[0..j]整体是s[0..i]的一个 border长度就是j1。3. KMP 匹配把失配变成跳转3.1 匹配主流程与双指针写法有了前缀函数数组KMP 匹配模式串pat在文本串text中的位置就有两种常见写法。第一种是拼接法构造str pat # text然后对整个str跑一次前缀函数只要某个位置的pi[i] pat.size()就说明text中以i - 2 * pat.size()为起点存在一个完整匹配。拼接法写起来非常短但有两个坑一是分隔符必须选一个在原串中不会出现的字符否则会跨过边界形成假的 border二是匹配起点下标要推准。我更推荐第二种双指针法省掉拼接和额外字符的隐患void kmp_search(const string text, const string pat, const vectorint pi) { int j 0; for (int i 0; i (int)text.size(); i) { while (j 0 text[i] ! pat[j]) { j pi[j - 1]; } if (text[i] pat[j]) { j; } if (j (int)pat.size()) { cout i - j 1 \n; // 匹配的起始位置 j pi[j - 1]; } } }整个匹配过程维护一个变量j表示“当前以text当前位置i为结尾最多能匹配pat的多长前缀”。这个概念很重要j不是“当前比较到哪个模式串下标”而是“已匹配长度”。正因为是长度所以失配时跳转要用pi[j-1]而不是pi[j]——举个例子j 3表示模式串前 3 个字符匹配成功我们需要知道这 3 个字符组成的子串pat[0..2]的最长 border 长度自然就是pi[2]也就是pi[j-1]。3.2 一个完整的匹配模拟与失配跳转演示拿文本串text abababcab模式串pat abab来手动模拟一遍体会失配时跳转的效果。先算pat的前缀函数pi [0, 0, 1, 2]。匹配过程如下i 0text[0] a与pat[0]相同j 1。i 1text[1] b与pat[1]相同j 2。i 2text[2] a与pat[2]相同j 3。i 3text[3] b与pat[3]相同j 4。此时j pat.size()找到一个匹配起始位置3 - 4 1 0。输出后j pi[3] 2意思是“匹配结束后模式串还有长度为 2 的后缀ab可以复用”。i 4text[4] a比较pat[2] a匹配j 3。i 5text[5] b比较pat[3] b匹配j 4。又完整匹配起始位置5 - 4 1 2。输出后j pi[3] 2。i 6text[6] c比较pat[2] a不匹配执行whilej pi[1] 0再比较pat[0] a与c还是不匹配退出循环。i 7text[7] a比较pat[0]匹配j 1。i 8text[8] b比较pat[1]匹配j 2。循环结束。最终找到两个匹配位置0 和 2。看整个过程的关键在于i 4, 5时我们没有重新比较ab而是利用上次匹配结束后遗留的j 2直接接着匹配后缀。这就是 KMP 快的原因文本串指针永不回退模式串指针通过前缀函数来回退回退量是已经验证过的信息不需要重新比较。文本串和模式串都只有几万个字符的时候暴力的代价还不明显一旦到了百万、千万级别O(n*m)和O(nm)就是天壤之别。这也是为什么 KMP 是“字符串匹配必学算法”的根本原因。3.3 next 数组的版本之争这个点值得单独拎出来说因为太多人在网上搜“KMP next 数组计算”搜出来的代码五花八门越看越糊涂。根源在于next 的定义在学术界和竞赛圈、考研教材、网上博文之间并不统一。先明确我们这里用的是前缀函数pi[i]含义是s[0..i]的最长 border 长度。它下标从 0 开始且不包含“失配后跳转到哪里”的语义只描述结构。而很多教材里的next数组有两种常见改写把pi整体右移一位next[i] pi[i-1]并令next[0] -1。这种写法在“按下标从 1 开始”的字符串里很常见失配时直接j next[j]即可不需要减一。部分资料把next[i]直接定义为“当第i位失配时应跳转到的下标”也即是上面右移版本。这两种写法都不是错的它们只是为了让失配跳转的代码写起来更顺手。真正的问题在于你如果只背写法不理解pi的原始含义换一道题、换一个下标起点就露馅。我的建议是统一使用带pi的版本失配时写j pi[j-1]匹配时下标 0 基准。理由有三它最不容易出边界错误pi的有效索引从 0 到n-1每一步都有定义。字符串周期、border 链等扩展用途全部依赖pi这个原始定义改写成别的 next 还要再换算回来反而麻烦。面向竞赛的模板题和算法库绝大多数都是基于前缀函数写的对拍也好、查资料也好口径一致。你只要记牢一点“当前已匹配长度是 j失配时看的是长度为 j 的前缀的最长 border所以取pi[j-1]”。这个逻辑链条想通了任何版本的 next 你都能现场推出来不用背。4. 字符串周期KMP 的第二个杀手锏4.1 周期、循环节与 border 的数学关系字符串s长度是n。如果存在一个正整数p使得对所有的i ∈ [0, n-p-1]都有s[i] s[ip]那么p就是s的一个周期。注意这里p不一定要整除n——这一点非常重要它是“周期”和“循环节”的差别所在。举个直观的例子s abcabn 5。取p 3检查s[0]a和s[3]a相等s[1]b和s[4]b相等对s[2]没有对应的s[5]需要比较所以p 3是一个周期。但3不能整除5所以s不能说成是某个循环节重复两次得到的串我们只称3为它的周期而不叫最小循环节长度。周期和前缀函数有什么关系设s有长度为l的 border也就是s[0..l-1] s[n-l..n-1]。令p n - l那么对任意i n-p有s[i] s[ip]——因为这两个位置关系恰好落在 border 等式的错位比较上。所以border 越长对应周期越短。最长 border 对应最小周期这是理解字符串周期的钥匙。4.2 最小循环节公式与判定模板基于上面的关系经典结论是字符串s的最小循环节长度指能整除n的最小周期为r n - pi[n-1]如果n % r 0那么r就是最小循环节长度且s可以完全由若干个长度为r的前缀重复拼接而成如果n % r ! 0则不存在任何真循环节整个串只能看成一个循环节即没有“由重复子串完整构成”的写法。代码非常短int n (int)s.size(); vectorint pi prefix_function(s); int r n - pi[n - 1]; if (n % r 0) { cout r \n; // 最小循环节长度 } else { cout n \n; // 没有完整循环节 }为什么整除条件这么关键用前面的abcab来算pi[4] 1最长 border 是首尾的a仔细看abcab的前缀ab与后缀ab也相等长度为 2所以pi[4] 2r 5 - 2 35 % 3 ! 0所以它没有完整循环节——和我们的判断一致。再算一个能整除的例子s ababab。n 6最长 border 是abab长度 4r 6 - 4 26 % 2 0最小循环节就是2也就是ab整个串是ab重复 3 次。这个结论还可以推广n / r就是这个串最多能拆成的重复次数。4.3 周期问题的经典变形与技巧掌握了最小循环节很多字符串题目就变成了模板题上的简单应用。常见的变形有这几种判断一个串是否完全由一个子串重复得到。方法就是上面说的检查n % (n - pi[n-1]) 0是否成立成立则说明能完整重复。注意边界串长为 1 时r 1 - 0 11 % 1 0一般认为单字符也是自身的循环节。求所有可能循环节长度。这需要遍历 border 链。pi[n-1]是最长 border 长度它的次级 border 是pi[pi[n-1] - 1]再往下一层是pi[pi[pi[n-1]-1] - 1]直到 0。沿途每个n - border_len如果满足整除条件就是一个可能的循环节长度。找所有循环节、找所有 border 实际上和找所有周期是同一个问题的两面。两个相同串拼接去头尾找模式串。这是一个经典技巧如果想知道某个串的循环性质可以把s拼成s s去掉第一个字符和最后一个字符然后在里面搜索s的匹配次数。这种方法在某些字符串构造问题里特别方便本质还是利用 KMP 的匹配能力判断周期是否存在。结合哈希做快速周期判定。虽然题目往往限制用 KMP但理解周期后你会发现判一个子串是否有周期、周期是多少也可以用字符串哈希配合长度枚举来做。KMP 的优势是线性复杂度、常数小、自带 border 链但是在需要在线段树或树上维护动态周期信息的场景哈希才能灵活配合两者最好都掌握。5. 常见问题与坑位实录5.1 下标从 0 还是从 1边界全线崩溃这是 KMP 相关题目里最经典的翻车点。很多人字符串习惯从 1 开始读cin s 1前缀函数写法也跟着改成pi[i]表示前i个字符的 border 长度。此时失配跳转写成j pi[j]而不是pi[j-1]匹配成功判定变成j m之后输出i - m 1。两种下标体系都对但不能混用。我在对拍时见过最多的错误就是代码里字符串是 0 基的但失配跳转写成j pi[j]或者反过来。排查方法很简单用abab这个模式串在ababab里搜一遍如果第二个匹配位置没输出多半就是下标转换出了问题。建议初期不要用偏移技巧老老实实 0 基 pi[j-1]等熟练了再适应别的写法。5.2 拼接法里分隔符翻车拼接法pat # text里唯一的分隔符看起来随意实际上非常讲究。如果题目给定的字符串范围明确说明只含小写字母那#完全安全但如果字符集是任意可见 ASCII或者数据里明确可能出现#你就不能用拼接法或者需要改用一个不可能出现的字符。踩过一次坑当时题目字符是a-z和A-Z我图省事用了#结果样例全过交上去 WA 一片。对拍才找到问题——某个测试点里文本串包含aaaa#aaaa#两边完美形成 border前缀函数直接算出虚假匹配。解决方案有两个要么改用双指针法从结构上就不需要分隔符要么用特殊哨兵字符比如字符串类题目里可以用\0或者 ASCII 表里不属于合法输入的字符前提是你清楚输入数据的具体约束。5.3 自测数据与对拍方法代码写完之后强烈建议自己跑几组边界数据而不是只看样例。我用过的最高效的方法是对拍写一个暴力匹配函数再跑 KMP随机生成数据比较结果。下面几个边界数据是必测的模式串长度为 1text aaaaa, pat a输出应该是 5 个位置。模式串全相同text aaaaaa, pat aaa输出应该是 4 个位置这最能检验失配后跳转是否写对。模式串和文本串完全相同应该输出一个位置 0。模式串长度大于文本串应该什么都不输出这里特别容易因为循环条件写错而越界。空串如果题目允许字符串函数要提前处理n 0否则pi[n-1]直接越界。对拍的时候别用固定的rand()简单生成要混合生成一部分数据全由同一个字符组成一部分由两三个字符随机组成一部分字符集极小如只有a和b这样能更快逼出边界错误。我曾经用这招一晚上抓出自己三个版本的 KMP 写法各自的坑。5.4 性能与输入输出的隐藏问题KMP 的复杂度是线性的但实现的时候仍然有性能损耗的隐藏点。第一个是输入输出同步cin/cout默认会和stdio同步大量输出匹配位置时会很慢加两行ios::sync_with_stdio(false); cin.tie(0);效果立竿见影。第二个是字符串复制拼接法里string total pat # text;会复制整个文本串如果文本串是百万级开销不小能接受但要注意内存双指针法则完全没有这个问题。第三个是vectorint pi的重复创建如果你要在一个程序里对多个模式串算前缀函数提前reserve可以省掉反复扩容的开销不过一般规模下差别不大不强迫。还有一个我个人的经验模式串的前缀函数只需要算一次不要在匹配循环里重复调用。很多新手会写一个get_next(pattern)然后每次失配时调用把O(m)的预计算变成O(n*m)的最坏情况直接废掉 KMP 的线性优势。保证整体结构是“先算 pi再跑匹配”这是模板题的基本素养。写这套东西到现在我自己最深的体会是KMP 不是一个需要背的模板而是一个需要理解“前缀函数如何描述字符串自相似性”的思想工具。前缀函数、匹配、周期这三件事底层是同一个数组在三个场景下的投影。每次写模板题之前先默写一遍前缀函数而不是直接抄匹配代码然后你会发现后面的 KMP 和周期其实就只剩下二十行收尾工作了。如果你正在学这块内容不妨把 S001 这个模板题用自己的语言重写一遍再拿几个边界数据测一测跑通后再去看字符串哈希、AC 自动机会有种突然通透的感觉。这个板子练熟了后续很多字符串算法都能少走很多弯路。