刷字符串题的人迟早会和HDU 3746 这道 Cyclic Nacklace 碰面。题目名看着花哨核心就一句话最小循环节。给你一个字符串问至少补几个字符才能把它变成一个“某个更短子串重复若干次”的循环串。比如abcab补一个c变成abcabcababa补一个b变成ababab而abcabc本身就是循环串补 0 个。解法并不神秘靠的就是 KMP 里的 next 数组。我做这题时卡了两天公式len - next[len]背得下来但始终没想明白它为什么是“最小”循环节也搞不清next[len] 0时到底该输出什么。这篇就把题意、推导、实现和坑一次性讲透适合刚学完 KMP、准备拿循环节练手的读者也适合想把这题模板化的刷题党。1. 读懂题意先搞清楚“循环”到底指什么1.1 循环串的条件我们说的“循环串”指的是一个串能写成某个更短串重复多次的形式。abcabcabc可以看作abc重复三次aaaa可以看作a重复四次ababab可以看作ab重复三次。核心条件是这个串的最短重复单元长度必须能整除串长。abcabc长度 6重复单元abc长度 36 能被 3 整除完美循环。但abcabca长度 7重复单元abc长度 37 不能被 3 整除所以它不是完整的循环串只是某个循环串的前缀缺了bc补上 2 个字符就能变成abcabcabc。“至少补几个字符”本质上是先找到那个最短重复单元再看当前串末尾缺了多少。最短重复单元就是标题里说的“最小循环节”。找到最小循环节是这道题唯一的目标剩下的只是除法和减法。1.2 输入输出与数据范围隐藏的信息HDU 3746 的输入模式很经典第一行一个正整数 T表示测试组数接下来 T 行每行一个字符串全部由小写字母组成长度在 1 到 100000 之间。对每个字符串输出一行整数表示最少需要补的字符数。几个容易被忽略的细节字符串长度是 1e5 级别暴力做法无论如何过不了。最直接的暴力是枚举所有可能的循环节长度对每个长度做一次 O(n) 校验乘起来 O(n^2)1e5 长度直接超时。多组数据意味着每次要重新计算 next 数组不能把上一组的结果带过来。输出的是“补多少”不是“循环节长度是多少”很多人公式推对了最后一步取模取反却搞反了。这道题的数据范围基本就是在暗示用 KMP 的 O(n) 预处理拿 next 数组然后用一个 O(1) 公式出结果。2. next 数组KMP 里被低估的那个数2.1 next 数组的真实身份是“最长公共前后缀”KMP 的 next 数组很多教材叫法不一样有的叫 fail 数组有的叫前缀函数。不管叫什么它记录的都是同一个东西对于模式串前 i 个字符组成的子串它的最长公共前后缀长度是多少。公共前后缀有个更专业的名字叫 border。一个串的 border是既是它前缀又是它后缀的真子串。比如ababa前缀有a、ab、aba、abab后缀有a、ba、aba、baba公共部分是a和aba最长的是aba长度 3所以next[5] 3。关键是next[len]这个值它表示整个字符串的最长 border 长度。比如abcabca前缀abca和后缀abca相等没有更长的公共前后缀所以next[7] 4。这个值就是整道题的题眼最小循环节完全由它决定。2.2 传统 KMP 写法的 next 计算细节HDU 这代 OJ 的题目用 C 的char[]加scanf是最稳的组合。next 数组的写法有很多流派我用的这套是-1开头的经典写法#include cstdio #include cstring const int MAXN 100010; char s[MAXN]; int nxt[MAXN]; void getNext(char *p) { int n strlen(p); nxt[0] -1; int i 0, j -1; while (i n) { if (j -1 || p[i] p[j]) { i; j; nxt[i] j; } else { j nxt[j]; } } }这个写法里i是当前处理的字符位置j是已经匹配上的 border 长度。当字符相等i和j一起前进nxt[i]记录下当前 border 长度当失配j回退到nxt[j]继续尝试更短的 border。循环结束时nxt[n]就是整个串的最长 border 长度。注意nxt数组要开到len 1因为我们要访问nxt[n]。很多人这里开成MAXN 100000刚好够存字符串但nxt[100000]就越界了改成100010就安全得多。2.3 前缀函数写法与 -1 写法的对应还有一部分人学的是前缀函数写法pi[0] 0pi[i]表示前 i1 个字符的最长 border 长度。这种写法里整个串的最长 border 是pi[n - 1]最小循环节就是n - pi[n - 1]。两种写法本质等价但千万别混用。我之前见过有人拿前缀函数的模板却用nxt[n]去取答案结果边界上差了一位怎么调都错。选定一种写法后整道题所有的索引都要围绕它来。3. 最小循环节公式len - next[len] 是怎么来的3.1 核心公式的直观推导假设字符串长度是 nnext[n]是整个串的最长 border 长度 b定义 L n - b也就是标题里说的最小循环节长度。为什么 L 是循环节因为 border 的含义是前 b 个字符和后 b 个字符完全相同。把字符串画成一条线从开头数 b 个字符和从末尾倒数 b 个字符这两段是重合的。由于 b n - L前面 b 个字符就是从 0 到 n-L-1后面 b 个字符就是从 L 到 n-1这两段相等意味着从位置 0 开始的字符串和从位置 L 开始的字符串在长度为 b 的范围内逐字符相同。换个容易理解的说法把整个串“错开 L 位”叠在一起重合的部分完全一样。这就说明每隔 L 个字符字符就会重复一次串就是由长度为 L 的片段不断重复可能最后一段不完整构成的。所以 L 是一个循环节长度。再解释“最小”循环节越短对应的 border 就越长因为循环节长度 L 与 border 长度 b 满足 L b n。如果存在比 L 更短的循环节 t那它对应的 border 长度就是 n - t这个值比 n - L 更大就存在比next[n]更长的 border与“next[n] 是最长 border”矛盾。所以n - next[n]一定是最小循环节长度。3.2 分情况讨论完整周期、残缺周期、完全没有周期拿到最小循环节 L 之后原串有两种命运。第一种n 能被 L 整除。此时原串是 L 的整数倍重复本身就是完整的循环串不需要补任何字符答案是 0。abcabcabc的next[9] 6L 39 能被 3 整除输出 0。第二种n 不能被 L 整除。原串是循环串的“残缺前缀”比如abcabca是abcabc加一个a差bc没补完。需要补的字符数是 L - (n % L)把最后一段补齐。算一下abcabcan 7next[7] 4L 3n % L 1补 3 - 1 2 个字符变成abcabcabc。这里埋着一个最大的坑next[n] 0时L nn % L 恒等于 0按第一种情况会错误地输出 0。但abc这种串没有任何 border它的最小循环节是它自己因为“只有一段”不能算循环串至少要有两段才能叫循环。所以next[n] 0必须单独输出 n意思是再补一整个串的大小。也正是因为这一点很多人第一次写这道题时数据一大就挂。3.3 三种状态速查表状态判断条件输出完整循环串next[n] 0且n % (n - next[n]) 00有 border 但残缺next[n] 0且n % (n - next[n]) ! 0(n - next[n]) - n % (n - next[n])完全没有 bordernext[n] 0n这张表建议直接抄进代码注释里写的时候对着看比凭记忆判断稳得多。4. 完整代码与实现细节照着写就能 AC 的模板4.1 可提交的完整代码下面这份代码是我当年调试通过后一直留着的模板注释已经把分支逻辑写清楚直接提交就能用#include cstdio #include cstring const int MAXN 100010; char s[MAXN]; int nxt[MAXN]; void getNext(char *p) { int n strlen(p); nxt[0] -1; int i 0, j -1; while (i n) { if (j -1 || p[i] p[j]) { i; j; nxt[i] j; } else { j nxt[j]; } } } int main() { int T; scanf(%d, T); while (T--) { scanf(%s, s); int n strlen(s); getNext(s); if (nxt[n] 0) { printf(%d\n, n); continue; } int cycle n - nxt[n]; if (n % cycle 0) { printf(0\n); } else { printf(%d\n, cycle - n % cycle); } } return 0; }整个代码的核心只有十几行真正的难点全在理解和边界判断上。建议把getNext背熟循环节这部分逻辑自己手写因为比赛里类似的变形题很多背模板容易把分支条件记串。4.2 现场踩过的坑第一坑数组大小。字符串长度最大 1e5但nxt需要访问nxt[n]所以数组必须开到至少 100001。我一开始开成100000本地小数据全过一上 OJ 就偶发越界调了半天才发现是数组下标问题。第二坑输入输出。HDU 这种老 OJ 对速度有要求用cin读 1e5 长度的字符串T 一大就容易卡。老老实实用scanf(%s, s)。gets已经被移除了也别用。第三坑next是某些编译环境里的保留字变量名最好写成nxt免得跟系统函数冲突。这是个很小的点但能省一次编译报错。第四坑多组数据之间的数组残留。我的写法里nxt每次都被重新覆盖不会残留旧值影响结果。如果用别的方式初始化记得确认每组数据之间不会串值。4.3 手推三个测试点验证拿abcabca手动走一遍。字符串长度 n 7求 next前缀abca和后缀abca相等且最长所以nxt[7] 4cycle 7 - 4 3。7 % 3 1输出 3 - 1 2正确补bc得到abcabcabc。再走aaa。n 3nxt[3] 2cycle 13 % 1 0输出 0本身就是a的循环串不用补。最后走ababa。n 5最长 border 是aba长度 3nxt[5] 3cycle 25 % 2 1输出 2 - 1 1补一个b得到ababab。三个例子覆盖了“残缺补齐”“完整循环”“有 border 但长度不整除”三种情况加上next[n] 0这种特殊情况基本上所有分支都验证过了。5. 错误答案排查常见的五种翻车现场5.1 症状与原因对照表症状可能原因修复方式abcabca输出 0 而不是 2没有特判next[n] 0之外的整除误判或者n % cycle 0判断写错按速查表分支顺序检查全部样例输出偏大next数组求的是最长公共前后缀但代码里把失配回退写成了j--回退必须写j nxt[j]单个字符a输出 0nxt[1] 0cycle 1n % cycle 0误判特判nxt[n] 0输出 n大数据段错误数组开小了nxt[n]越界MAXN开到字符串长度 10答案有时差 1前缀函数写法和-1写法混用统一用一种取nxt[n]还是pi[n-1]要对应5.2 如何验证“最小”这个要求很多人写完代码样例过了就交结果 WA。问题往往出在“最小”两个字上你找到的循环节是不是真的最短验证方法很直接拿到一个输出结果后把补完的字符串在草稿纸上写出来数一数它是不是真的能由某个更短的子串完整重复。比如ababab如果代码输出的是 0你得确认它不能拆成更短的ab之外的单元重复。如果能拆成更短的说明你的next数组求错了。还有一种更严谨的自测方式写一个暴力程序枚举所有可能的循环节长度从 1 到 n对每个长度判定整个串能否由它重复构成然后跟 KMP 代码的输出对拍。小数据随机生成几千组两边答案一致基本就稳了。我之前所有字符串题都会配一个对拍器这是排查公式类错误最省力的手段。5.3 自测数据集这几组数据覆盖了所有分支可以拿去直接验证输入输出a1aa0ab2abc3aba1abcab1ababa1abcabc0abcabca2ababababa1aba这组容易算错n 3nxt[3] 1cycle 2n % 2 1补 1 个b变成abab。注意补完后是ab的循环不要误以为补a也行补a得到abaa根本不是循环串。6. 从这道题出发循环节还能怎么用6.1 判定“能否由某个子串重复构成”HDU 3746 的姊妹问题是给定一个字符串问它最多能由哪个子串重复构成也就是求最大重复次数。这类题的核心公式还是n / (n - next[n])前提是n % (n - next[n]) 0。如果整除重复次数就是商如果不整除说明不能由某个子串完整重复构成。这个结论可以直接迁移到很多字符串判定题上。比如判断一个字符串是不是由某个单词重复组成或者判断一段 DNA 序列是否由某个片段周期性拼接而成本质都在做同一件事求next[n]然后做一次整除判断。6.2 从“补全”到“删除”的变形“最少补几个字符”可以反向变成“最少删几个字符让剩余部分成为循环串”。这类题比补全难因为删除点不固定需要考虑从哪里断开。但分析的第一步仍然是求出整个串的最长 border 和最小循环节先搞清楚原始结构再枚举删除对 border 的影响。还有一类题问“最长循环子串”比如在一个大串里找一段最长的、由同一子串循环构成的子串。这类题又能用后缀数组或哈希配合二分但基础概念还是循环节。可以说最小循环节的思维是这一整类问题的地基HDU 3746 就是最省事的地基练习。6.3 border 结构在其他算法里的影子next 数组其实就是一棵“border 树”上的父指针fail 指针指向的是当前前缀的最长 border。很多字符串题里要用到 fail 链上的跳转比如 AC 自动机、KMP 自动机、回文串相关的 border 结构都和这道题里 next 数组的用法同源。对初学者来说不建议一上来就追这些高级结构。把 HDU 3746 的推导过程吃透遇到任何“重复”“周期”“border”相关的题第一步都问问自己next[len]是多少这条思路能帮你少走很多弯路。我第一次做这题时公式背下来了但始终觉得代码里的分支是凑出来的。后来把abcabca这种串在手写板上画了几遍把“错开 L 位后重合”这个直觉彻底想通了才真正记住这套东西。现在遇到循环节类的题我不会急着写代码而是先在纸上标出最长 border 在哪、循环节是谁确认清楚再动键盘。这个习惯帮我避开了很多边界错误。如果你也在循环节上卡过壳不妨也从手动推一个串开始把next数组一位一位算出来再回头看你写的代码会有一种突然开窍的感觉。