KMP最小循环节：next数组如何求解字符串补全问题

我第一次刷到 3746 这道题的时候以为它就是一道普通的字符串构造题。题目背景很简单一条项链上串着若干字符现在只允许在项链的一端接新的珠子问最少补多少个字符才能让整条项链变成某个循环子串反复出现的样子。这个“循环”还不是一般的重复而是要求至少循环两遍。看懂题面之后我随手敲了一版暴力结果 WA 得莫名其妙。后来才明白这道题表面考构造实际上考的是 KMP 中 next 数组背后那个最长相等前后缀的几何意义最终要你算一个东西——最小循环节。本文适合两类人。一类是刚学完 KMP、想在真题里检验理解的选手另一类是刷题时见过 3746 的题号、却一直没搞懂为什么答案代码那么短的人。全文从一个容易被忽略的问题讲起“最小循环节”这个名词到底是怎么从字符串的前缀和后缀里长出来的。我尽量把每一步推导摊开包括那些在网上解法里被一笔带过的边界情况。1. 题面读透环形项链为什么可以等价成一条字符串1.1 题目到底在问什么题目场景是项链。一串珠子排成一个环每个珠子上有一个小写字母。现在手头有一堆散珠只能往项链的一端首或尾接接完之后项链仍然是一条环。要求最终形成的环形串能由某个长度更短的子串循环重复至少两次得到。问最少加几个珠子。这个场景很自然但一旦进入字符串模型就会遇到一个容易忽略的细节环形项链没有“开头”和“结尾”。可题目又偏偏规定只能在某一个固定的缺口处往单侧补字符。这什么意思我见过很多选手在这里卡住甚至怀疑题目描述有误。实际上题目把“环”等价成了“一条从缺口展开的线性字符串”而补字符也只能加在这条线性串的右端。所以整个问题就变成给定字符串 S只能在 S 的末尾追加字符问最少添加多少字符能让新的串 S 满足“S 是某个子串 T 重复 k 次的结果且 k ≥ 2”。为什么要强调 k ≥ 2因为任何一个串都能被它自身“重复一次”构成如果允许 k 1答案永远都是 0题目就没有意义了。这是 3746 和很多类似题最大的一个隐含条件读题的时候一定要圈出来。很多第一次写的 WA 代码都是因为忘记了 k 严格大于 1。1.2 从“循环”到字符串模型的例子为了让这个转化更具体用一个实际的例子走一遍。如果 S abcabca肉眼观察“abc”重复两次是“abcabc”长度 6现在 S 长度 7尾部多了一个 a。我们需要在末尾补上 bc得到 abcabcabc这就是 abc 循环三次。所以答案是 2。如果 S aba补一个 b 变成 abab就是 ab 循环两次答案是 1。如果 S abcabc它本身已经是 abc 循环两次答案是 0。这三个例子刚好覆盖了三种情况部分重复但缺尾部、完全不循环、已经完整循环。前两个例子可以靠肉眼枚举但长度一旦到 10^5暴力枚举 T 的长度根本不可行。这正是 KMP 登场的原因。1.3 为什么暴力思路走不到最后最自然的暴力思路是枚举可能的循环节长度 p从 1 到 n然后检查 S 是否由长度为 p 的前缀重复若干次构成。每次检查是 O(n) 的总复杂度 O(n^2)n 到 10^5 就完全不可行。就算用字符串哈希把单次检查优化到 O(1)枚举 p 本身也要求 p 是 n 的约数可这里还有个麻烦S 当前可能不是一个完整的循环串需要“先补齐再检查”那么补多少并不是从约数枚举能直接看出来的。更隐蔽的问题是即使我们枚举出了一个 p让我们把 S 补到“长度是 p 的倍数”补出来的字符可能和 S 的尾部对不上。比如 S ababac如果我们天真地认为循环节是 2想把长度补到 8补出的串是 ababac??后两个字符必须满足“循环节 ab”的约束也就是要补 ab得到 ababacab但它依然不是 ab 循环构造的因为第 5、6 位是 a、c。这提示我们能不能补、补多少不是看当前长度离 p 的倍数还差多少而是看 S 的“尾巴”是否天然兼容这个循环节。KMP 的 next 数组恰恰能回答这个兼容性问题因为它记录了前缀和后缀的最大重叠。2. 最小循环节的一行公式len - next[len] 是怎么来的2.1 先弄清 border 和周期KMP 的 next 数组有很多种写法但最本质的是一个概念border。对于字符串的某个前缀它的 border 是指“既是这个前缀的真前缀、又是它的真后缀”的最长子串长度。比如 ababa 这个串的 border 是 aba长度 3因为 aba 既是串的前 3 位又是串的后 3 位内容完全一样。next[n] 常被定义为整个串的最长 border 长度。这个“最长”很关键。为什么题目只要最长不要其他因为我们要找的是最小循环节而循环节长度 n - border 长度这个等式的含义在下一小节展开。border 越长n - border 就越小。也就是说最大重叠对应最小循环节这是一个数学上的对偶关系。很多讲解把这层关系略过直接给公式结果就是读者会套代码但不会变通。2.2 重叠关系与公式的直观推导考虑一个长度为 n 的串 S假设它确实由某个短串 T 循环 k 次构成那么 T 的长度 p 满足 n k * p。现在把 S 从中间某个位置“切开”来分析 border。T 循环串有一个天然的 border长度 n - p。为什么因为 S 的前 n - p 个字符等于“循环了 k-1 次的 T”而 S 的后 n - p 个字符也等于“循环了 k-1 次的 T”这两个子串在位置上首尾错开了 p但内容完全一样。比如 S abababp 2n - p 4前缀 abab 和后缀 abab 一样所以 border 长度至少是 4。反过来想如果 S 存在一个长度为 L 的 border那就意味着前 L 个字符和后 L 个字符相同。把串 S 想象成两段长度都是 L 的重叠片段那么从 S 的开头开始每隔 n - L 个字符的内容就完全对齐一次。这一步直观上可以理解为border 越长两个重叠片段错开的距离 n - L 就越小而每次错开后的内容保持一致这正好是“循环”的特征。数学上可以严格证明当一个长度为 n 的串存在长度为 L 的 border 且 n%n - L 0 时该串就是由长度为 n - L 的前缀循环构成的。因此最小候选循环节就是 p n - next[n]next[n] 是最大 border 长度。这里我还故意加了“候选”两个字因为最后还要通过整除关系确认它是否是真正的循环节。整除才是最后一个检查点。2.3 不整除的时候尾部残缺与补全公式如果 p 恰好整除 n情况清楚S 已经是一个完整循环串。判断 k n / p 是否大于 1。大于 1 就直接输出 0等于 1 说明最小的“循环节”就是整个串自己那就要再补 p 个字符让整串循环两次。如果 p 不整除 n说明 S 当前处于一个“循环串缺了尾部”的中间状态。比如 S abcabcan 7p 37 % 3 1余数 1 表示现在已经有了一个完整的循环还多出了 1 个字符。我们要补上 p - (n % p) 3 - 1 2 个字符恰好补成完整的循环串。补上的字符是什么余数 1 的意思是最后那一个字符 a 是下一个循环节的第一个字符所以还差循环节的后两个字符 bc。这就把公式和字符串内容对应起来了。把这两种情况合并一下答案可以写成一个统一公式p n - next[n]如果 p 整除 n 且 n / p 1 则 ans 0否则 ans p - n % p。注意括号里的 p - n % p 在 n % p 0 时等于 p正好覆盖了“整串自循环一次”需要补一整个循环节的特殊情况。所以大部分代码里判断条件往往是先特判再输出结构更清楚。3. 代码落地与易错点next 数组写错一位答案差一个循环节3.1 为什么我推荐用“前缀函数”语义来写 nextKMP 的 next 大体有两个流派一个是教材常见的“失配回退下标”派初始 j -1 的那套另一个是竞赛里越来越常见的“前缀函数”派初始 next[0] 0每个位置存最长 border 长度。两种写法的计算结果在数值上有错位但本质等价。3746 这道题我强烈建议用前缀函数写法因为最终答案直接依赖 next[n] 这个值前缀函数写法的变量语义和“最大 border 长度”一一对应不容易在边界判断上出错。举个例子讲讲两种写法的差别。失配回退写法里next[i] 通常表示“模式串第 i 位失配时应该跳转到的下标”它和前缀函数数值可能差 1。如果你用那套模板做这题最终要取的可能是 next[n - 1] 再手动调整或者另开一个数组存完整串的 border。不是不能做只是每写一次都要在心里重新算一遍偏移。我见过不下十个选手在评论区问“为什么我的模板输出多了一个循环节”基本都是这偏移造成的。前缀函数写法里next[i] 存的是 S[0..i] 这个子串的最长 border 长度代码里直接取 next[n - 1]长度为 n 的整个串最后一个字符下标是 n - 1就是我们要的那个 L清爽得多。3.2 可在评测系统通过的完整实现下面给出 C 版本。多组输入 T每组读一个只含小写字母的串长度不超过 10^5整体复杂度 O(T * n)。#include bits/stdc.h using namespace std; const int MAXN 100005; int nxt[MAXN]; char s[MAXN]; int main() { int T; scanf(%d, T); while (T--) { scanf(%s, s); int n (int)strlen(s); // 计算前缀函数next[i] 表示 s[0..i] 的最长 border 长度 nxt[0] 0; for (int i 1; i n; i) { int j nxt[i - 1]; while (j 0 s[i] ! s[j]) j nxt[j - 1]; if (s[i] s[j]) j; nxt[i] j; } int loop n - nxt[n - 1]; // 最小候选循环节长度 int ans; if (n % loop 0 n / loop 1) { ans 0; } else { ans loop - n % loop; } printf(%d\n, ans); } return 0; }这段代码的答案分支只有 1 个分支不像网上有些写法要分三个 if 讨论原因在 2.3 已经解释过p - n % p 本身就兼容了“n % p 0 且倍数为 1”的情况。只要记住多补一整个循环节结果不会错。另外提一句前缀函数内部那个 while 循环用的是 nxt[j - 1]这是前缀函数标准写法如果你习惯失配回退派写成别的形式就要小心数组越界和取指差异。换写法时不要只改一行整套数组语义都要跟着变。3.3 四个特别容易踩的坑第一个坑是多组样例之间的 nxt 数组没有清空。这里其实不需要清空因为我们每次都从 i 1 开始重新计算到 n 结束nxt 的历史值会被覆盖但如果你在 getNext 函数里把 nxt 初始化放在函数外而某些分支提前 return 或 break就可能残留脏值。稳妥起见把 nxt[0] 0 写在循环体内开头即可。第二个坑是 n 为 1 的边界。此时 nxt[0] 0loop 1n % loop 0 且 n / loop 1不满足大于 1ans 1 - 0 1。答案是补 1 个字符比如 a 补成 aa符合“至少循环两次”。这算是一个很经典的 corner case很多人都挂在上面。如果不加 n / loop 1 这个条件ans 直接算成 0就 WA 了。第三个坑是 scanf 读空串。本题不会给空串但如果你在别的循环节题里用 gets 或 cin 处理遇到空行时会出问题。竞赛里统一用 scanf(%s) 最稳。第四个坑其实是理解层面的当 n % loop ! 0 时不要试图去枚举 n 的约数找更小的 p因为那个更小的 p 不满足“内容兼容”。比如 ababac 的 n 6算出来的 next[5] 0loop 6ans 6 - 0 6。也就是说整个串要补一个同样的串。这看着很怪明明前面“abab”看起来是循环的为什么答案是整整 6原因就是末尾的 c 打破了所有前缀对齐border 长度变成 0串无法与一个短周期兼容。此时想靠补字符“救回路”只能补一整个自身让它循环两次。这个反直觉的 case 很适合拿来提醒读者border 是全局信息不是局部信息尾部一个字符可以毁掉所有循环结构。3.4 一组覆盖典型情况的验证样例自己出题验证时我一般会写一个超小的暴力程序对照枚举循环节长度 p 并尝试补 0 个、1 个……p 个字符检查是否存在某个构造后串满足循环。暴力程序不需要复杂度低只用来对拍小数据。把对拍跑过几百组随机小串之后再提交上面的 KMP 版本基本就稳了。这里我把几个典型样例列出来方便你手动过一遍原串期望答案构造后的串说明a1aa单字符补一个形成两次循环aa0aa已经是循环两次abcabca2abcabcabc尾部缺了 bcaba1abab补成 ab 循环两次ababab0ababab已经是 ab 循环三次ababac6ababacababac尾部破坏循环只能整体重复xyz3xyzxyz完全不循环补一整个串这组测试覆盖了单字符、完整循环、尾部残缺、被破坏循环等几类典型情况。我用这几条数据在本地过了一遍答案全部与公式一致。4. 循环节问题怎么识别、怎么延伸由 3746 出发看一类题4.1 “循环节三件套”到底长什么样刷题多了一定会发现很多字符串题披着不同的外衣内核都是 n - next[n] 这一个式子。我管它叫“循环节三件套”第一最长 border 长度 L next[n]第二候选周期 p n - L第三整除判定 n % p 0。不管题目问的是“最少补几个字符”、“最多重复几次”还是“哪些前缀有循环节”全部落在这三句话里。比如经典题“求字符串中每个前缀的循环次数”枚举每个位置 i令 L nxt[i]p i 1 - L当 (i 1) % p 0 且 (i 1) / p 1 时前缀 S[0..i] 的最小循环节为 p循环次数为 (i 1) / p。这道题和 3746 的区别仅仅是“要输出循环次数”代码主干几乎一模一样。另有一道经典题“求一个串的最大重复次数”答案就是 n / p前提是 p 能整除 n本质上也是同一件事。把这些题放在一起对比着刷比单刷 3746 的记忆效果强得多。4.2 三个变式场景的思考方向再往深处看一眼。有些题会把循环节概念藏得更隐蔽。比如给定两个字符串 A 和 B问最短的串 C 是什么使得 C 能同时由 A 和 B 分别循环构造出来。这类题需要你分别算出 A 和 B 的最小循环节 p1、p2C 的循环节必须是 p1 和 p2 的某种最小公倍数关系本质上还是“整除”在起作用。又比如有些字符串压缩题给定一个串把它拆成最少个循环串段每一段都可以用 KMP 求一次最小循环节复杂度 O(n^2) 可优化成线性扫描加单调栈但核心判断函数永远是那三件套。还有一类题会要求在线查询某个子串是否循环这时需要对字符串建后缀自动机或哈希表再用“长度整除关系 border 相等”去判但最小候选周期依旧是端点间的 next 之差。我说的这些不需要现在全部掌握但知道同一个 root 能长出这么多题是刷题视野的一种提升。4.3 实战建议什么时候该想到 KMP 的 next这里给一些主观但实用的经验。第一题目里出现“循环节”“周期”“重复串”这些词优先想到 KMP 的 next。第二题目说“只能在一端添加字符”或“只能在尾部添加字符”这基本就是 3746 的同义改写十有八九是求 n - next[n] 的补全量。第三题面给了一个环、一个列表却只让你在某个切口操作那多半是想考线性字符串建模不要真去写循环链表的模拟。第四如果复杂度要求是 O(n) 且字符串长度到 10^5 甚至 10^6不要考虑后缀数组KMP 的 next 必须是第一反应。至于要不要为了这题去专门学一下 Z 函数实话说Z 函数也能求最长 border但在这类“补字符”问题里KMP 的 next 已经是最直接的工具再引入 Z 函数属于重复造轮子。如果你已经会用 Z 函数也可以作为自测的第二种解法如果还没学根本不需要为了这一题额外学。工具不在多关键是把 next 数组理解到什么程度。最后分享一个我自己的习惯遇到 3746 这种题目我从来不会直接交网上抄来的 next 模板而是先把loop n - nxt[n - 1]写出来然后用三个小样例自测单字符、完整循环串、尾部缺一个字符的串。这三样过了边界基本就安全了。这个习惯帮我省下了无数次 WA 之后翻讨论区的尴尬。希望这篇把 next 数组的“重叠”含义讲清楚之后你也能形成自己的验证套路。