1. 为什么字符串匹配非得从前缀函数开始字符串匹配这个需求写业务代码时一年碰不上几回可一旦碰上——比如在日志系统里过滤敏感词、在编辑器里做高亮、在基因序列里比对片段——暴力一个个比立刻让你怀疑人生。KMP 算法和它的前缀函数也叫失配函数、border 数组、教材里的 next 数组就是解决这类问题的经典模板。这篇我按“前缀函数 → KMP 匹配 → 字符串周期”的顺序把整条链路讲透中间会把 next 数组的几种计算方法、教材写法与工程写法的差异、以及我调模板时踩过的坑一并交代清楚适合算法入门、竞赛选手和面试前突击三类人看。1.1 前缀函数的定义排除“平凡自匹配”的那一刻开始前缀函数针对字符串的每个前缀求一个长度对于 s 的前缀 s[0..i]找一个最大的 k要求 s[0..k-1]长度为 k 的前缀恰好等于 s[i-k1..i]长度为 k 的后缀并且 k 不能取 i1。为什么必须排除整个串自身因为任何一个前缀的前缀和后缀都等于它自己如果允许 k i1那么所有 pi[i] 都直接等于 i1数组就完全失去信息量。我们关心的是“真正能复用的重叠部分”所以必须限定真前、后缀。这个定义对应教材里的一个词border。border 就是“既是真前缀又是真后缀”的子串。前缀函数 pi[i] 就是在说s[0..i] 的最长 border 长度是多少。理解成“回退地图”更好懂你已经匹配到第 i 位这个值告诉你在已匹配的部分里最长能保留多少字符继续和接下来的文本对齐不用从头再来。1.2 手工算一遍 pi比背十遍公式都管用以经典例子 s ababaca 手动推一遍i前缀 s[0..i]最长相等真前后缀pi[i]0a无01ab无02abaa13ababab24ababaaba35ababac无06ababacaa1所以 pi {0, 0, 1, 2, 3, 0, 1}。光看数字很抽象但换成场景就清楚了假设模式串匹配文本到第 4 位说明已经匹配出 ababa这个前缀里 aba 既是头又是尾失配时模式串整体向右滑等于只丢掉 ab 两个字符“aba” 这段仍然对齐着直接从那之后继续比较。这就是 KMP 比暴力快的原因——它从不回头重复比较已经确认相等的字符。2. 线性求前缀函数回退链如何做到均摊 O(n)2.1 核心递推border 的 border 还是 border暴力求 pi 是从大到小枚举 k 逐个验证最坏 O(n^2)等于白搭。线性方法的思路是站在之前的结果上往后推。设 pi[i-1] j说明 s[0..j-1] 是 s[0..i-1] 的最长 border。现在考虑新字符 s[i]如果 s[i] 恰好等于 s[j]那可以直接“延长”这个 border得到 pi[i] j 1。如果不相等我们需要在更短的 border 里找机会。这里的关键问题是下一个候选长度去哪找答案是 pi[j-1]。原理是一个漂亮的传递性质border 的 border仍然是原字符串的 border。s[0..j-1] 是 s[0..i-1] 的 border那么 s[0..j-1] 的 border长度 pi[j-1]既是 s[0..j-1] 的前缀又是它的后缀而后缀部分又接在 s[0..i-1] 的后缀里于是它同时是整段前缀的前缀和后缀——合法候选成立。这个链式回退保证不遗漏任何可能又能让候选长度快速收缩是整套算法的灵魂。2.2 模板代码与复杂度拆解下面这版是我默认在用的0-basedC没有任何多余操作vectorint get_pi(const string p) { int m (int)p.size(); vectorint pi(m, 0); 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; } return pi; }逐行解释pi[0] 固定为 0i 从 1 开始j 先继承上一轮结果while 做链式回退直到 p[i] 能和 p[j] 对上最后 if 判断能不能扩展 1 位。复杂度是均摊 O(m)i 每轮最多让 j 增加 1整个过程中 j 的增量总数不超过 m而 while 每执行一次 j 至少减 1j 又不可能为负所以回退总次数也被 m 限制住。两头一夹总操作数 O(m)。Python 版本逻辑完全一致只是语法换了def get_pi(p: str) - list[int]: pi [0] * len(p) for i in range(1, len(p)): j pi[i - 1] while j and p[i] ! p[j]: j pi[j - 1] if p[i] p[j]: j 1 pi[i] j return pi另外值得记住一点pi 数组只依赖模式串不依赖文本。这决定了 KMP 可以做流式匹配——文本多长都不影响内存只要存模式串的 pi就能一边读文本一边出结果。3. KMP 匹配主流程next 数组的三种写法一次说清3.1 匹配主循环失配时模式串滑到哪建好 pi 之后匹配过程就是把“模式串已匹配长度 j”当作状态。比较 t[i] 和 p[j]相等就 j失配就把 j 退到 pi[j-1]相当于模式串整体右滑让已匹配部分里的最长 border 重新对齐再继续比较。这个回退逻辑和 build 阶段一模一样只是比较对象从模式串自己换成了文本和模式串。vectorint kmp_match(const string t, const string p) { vectorint pos; int m (int)p.size(); if (m 0) return pos; vectorint pi get_pi(p); int j 0; for (int i 0; i (int)t.size(); i) { while (j 0 t[i] ! p[j]) j pi[j - 1]; if (t[i] p[j]) j; if (j m) { pos.push_back(i - m 1); j pi[j - 1]; // 继续找重叠/后续匹配 } } return pos; }匹配成功后不要急着把 j 清零j pi[j-1] 是为了不遗漏重叠出现的情况。比如在 aaaa 里找 aa正确结果是 0、1、2 三个位置如果清零只会得到 0、2 两个。很多新手在这里翻车因为样例里正好没有重叠匹配导致隐患一直藏到大数据才爆出来。3.2 教材 next / nextval 与 pi 的换算关系如果你是从严蔚敏那版教材学的 KMP看到的可能是 1-based 的 next 数组甚至还有 nextval学生时代死记硬背的“next 计算”和现在我们写的 0-based pi 对不上很正常。先把结论摆出来教材的 next[1] 0对于 i ≥ 2next[i] 前 i-1 个字符组成的前缀的最长相等前后缀长度 1。换算成 0-based 的 pinext[i] pi[i-2] 1。用教材常客模式串 abaabcac 验证1-based 的 next {0, 1, 1, 2, 2, 3, 1, 2}0-based 的 pi {0, 0, 1, 1, 2, 0, 1, 0}逐位代进去完全吻合。教材引入 nextval 是为了再跳过一层如果回退后落到的字符恰好和失配字符相同下一次比较必然又失败不如直接继续回退。这个优化在 pi 版本里其实由 while 的链式回退天然吸收了不需要额外数组。经典教材的 next 计算代码注意 P 是 1-basedP[0] 不存内容void get_next(char P[], int m, int next[]) { int i 1, j 0; next[1] 0; while (i m) { if (j 0 || P[i] P[j]) { i; j; next[i] j; } else { j next[j]; } } }我把两种写法整理成一张对照表方便你随时查流派下标核心数组语义失配回退适合场景前缀函数 pi0-basedpi[i] 是最长相等真前后缀长度j pi[j-1]工程与算法题首选教材 next1-basednext[1]0next[i]pi[i-2]1j next[j]教材与考试nextval1-based在 next 基础上继续跳过相同字符j nextval[j]极端重复串我的建议很直接写题和工程里只用 pi 版本它天然避开 1-based 的无数 off-by-one。如果题目或面试故意考教材 next按表格里的换算关系手动推绝不要在代码里混用两套下标。3.3 拼接写法与分隔符之坑除了双指针匹配还有一大流派是“拼接 一次 get_pi”构造 s p sep t然后找 pi[i] m 的位置即匹配终点。代码短记忆成本低但有两个坑必须知道。第一个坑是分隔符。必须选一个绝不出现在 p 和 t 里的字符通常用 # 或 \0作用是切断模式串与文本之间、以及模式串内部跨边界的 border 干扰。只要文本里真的含有这个字符结果就会错乱而且很隐蔽。更稳的做法是不确定字符集就别用拼接法回到双指针如果字符串可能包含任意字节可以把 string 转成 vector 后用 -1 做哨兵。第二个坑是下标换算。拼接后串联串长度为 m 1 |t|pi[i]m 对应的文本起点是 i - 2*m这个“减两个 m”的式子我每次写都要心里过一遍于是干脆把它注释在代码里vectorint kmp_by_concat(const string t, const string p) { vectorint pos; int m (int)p.size(); if (m 0) return pos; string s p; s.push_back(\0); // 哨兵确保不出现 s t; vectorint pi get_pi(s); for (int i m 1; i (int)s.size(); i) if (pi[i] m) pos.push_back(i - 2 * m); // 对应 t 中的起点 return pos; }实测下来我对双指针版的信任度更高因为少一个“字符集不包含哨兵”的前提假设就少一类隐蔽 bug。4. 字符串周期用前缀函数一行判断最小循环节4.1 周期与 border 的一个等式字符串周期是前缀函数的另一个高频落点。字符串 s 的长度为 p 的周期按最常见的定义弱周期是对任意满足 ip n 的 i都有 s[i] s[ip]。通俗讲就是把字符串平移 p 格重叠部分完全一致。而 border 说的是前缀等于后缀。这两个概念实际上是一个等式存在长度为 k 的 border等价于存在周期 n-k。证明很直接设 s[0..k-1] s[n-k..n-1]令 p n-k则对于 i 0..k-1s[i] 恰好等于 s[ip]而 ip 的范围是 p..n-1正好覆盖所有需要验证的位置平移等式成立。反过来也成立有周期 p则长度为 n-p 的前后缀必然相等。所以“找所有周期 找所有 border”而所有 border 就是 pi[n-1] 不断沿 pi 链往前跳得到的序列。4.2 最小循环节判定模板“字符串是否由某个基本单元重复拼接而成”是周期问题最常见的形态力扣 459、POJ 2406 的 Power Strings、HDU 1358 的 Period 都是这类。判断只需要两行逻辑bool is_power_string(const string s) { int n (int)s.size(); vectorint pi get_pi(s); int unit n - pi[n - 1]; return unit n n % unit 0; }unit 就是最小循环节长度。为什么成立时 unit 一定是最小周期因为任何更短的周期都对应更长的 border而 pi[n-1] 已经是整个串的最长真 borderunit n - pi[n-1] 必然是最小弱周期。如果 n % unit 0说明字符串可以被等长切成整数块每块都等于 s[0..unit-1]完美循环成立如果不整除串只是“部分周期”现象。拿 abcab 举例pi[4] 2unit 3但 5 % 3 ! 0所以它有弱周期 3头和尾重合了 ab却不是某个单位的整串重复。这两者有本质区别做题前先看清题目要的是完整循环节还是任意弱周期。4.3 枚举全周期border 链的实际用法如果题目要输出所有可能的周期而不是只判断最小循环节就直接遍历 border 链vectorint all_periods(const string s) { int n (int)s.size(); vectorint pi get_pi(s); vectorint res; int k pi[n - 1]; while (k 0) { res.push_back(n - k); k pi[k - 1]; } res.push_back(n); // 自身也算周期 return res; }拿 abababab 实验n 8pi[7] 6border 链是 6、4、2、0对应周期 2、4、6、8。这说明它既能看成两个 abab 拼接也能看成四个 ab 拼接最小完整循环节是 ab。在一些需要枚举循环节或者检查“是否存在周期 p”的题目里直接拿这个数组做候选集速度和正确性都比哈希写法稳。5. 实战排错与经验备忘几个隐蔽 bug 和一个对拍技巧5.1 五个最容易出错的现场这些年我从自己和别人代码里见过的 KMP bug 高度集中整理成一个速查表症状根因一句解匹配结果少了重叠位置匹配成功后把 j 直接清零改成 j pi[m-1]偶发越界或死循环用 size_t 做下标j 减到 -1长度一律转 int 再算匹配数莫名偏多拼接法的分隔符与字符集冲突换哨兵或改双指针回退结果和预想不符pi[j] 与 pi[j-1] 用混回退永远是对已匹配长度 j 取 pi[j-1]模式串为空或长度为 1 时出怪结果没有单独特判m0 提前返回空长度 1 检查比较逻辑其中“回退用 pi[j-1]”这条最值得强调。你的已匹配长度是 j候选 border 长度当然取 pi[j-1]写成 pi[j] 读的是下一个位置的值既容易越界也可能恰好掩盖错误。无符号下标的问题也常见j 0 时再执行 j pi[j-1] 会把 j 变成极大无符号数轻则越界重则死循环所以我一律用 int 存长度。5.2 调试技巧与“什么时候别用 KMP”我每次写新版本都会顺手写一个十行的暴力对拍随机生成长度 1 到 20 的小写字母串暴力枚举起点统计匹配再和 kmp_match 的结果比对跑一万组。除了随机串固定测这四类边界全相同字符aaaaaa 找 aa、模式串等于文本、模式串比文本长、只有一个字符的文本。这一套能拦住绝大多数 off-by-one也适合新手自测。另一个容易被忽略的事实是KMP 的复杂度很稳但常数不一定比标准库 find 小因为很多平台的 find 做了底层向量化优化。所以别把所有字符串查找都替换成 KMP。什么情况才值得用你写的是算法题、模式串固定、需要严格线性复杂度、或者需要自己拿到所有匹配位置。模式串有多个时优先 AC 自动机而不是 KMP 的变体模式串频繁变化时字符串哈希可能更省事带通配符的匹配KMP 也帮不上忙去想想动态规划或者其他方案。5.3 把这套模板收进自己的工具箱我的做法是把 get_pi 和 kmp_match 两个函数固定存在代码片段里注释写清楚前置条件和注意事项。周期判断和枚举就是一行调用不值得单独记。下次遇到“找子串出现次数”“判断字符串是否循环”“求最小循环节”这类题直接调用把精力留给边界条件和业务逻辑。最后分享一个面试现场的小技巧要手写 KMP 时别从背代码开始先写出 pi 的循环头两行再对着“pi[i-1] 是上一轮最长 border”的语义把 while 补全最后写匹配循环。这个过程比默写整段会慢几秒但能大幅降低下标记错的风险而且向面试官展示你是真懂而不是背模板。毕竟这种基础算法考的不是“能不能跑通”而是“出问题能不能两分钟定位”。这套模板在我手里已经用了很久从竞赛到工程再到给别人讲都是靠 S001 这组函数撑起来的属于越用越稳的那种。
KMP算法与前缀函数：从字符串匹配到周期判断
1. 为什么字符串匹配非得从前缀函数开始字符串匹配这个需求写业务代码时一年碰不上几回可一旦碰上——比如在日志系统里过滤敏感词、在编辑器里做高亮、在基因序列里比对片段——暴力一个个比立刻让你怀疑人生。KMP 算法和它的前缀函数也叫失配函数、border 数组、教材里的 next 数组就是解决这类问题的经典模板。这篇我按“前缀函数 → KMP 匹配 → 字符串周期”的顺序把整条链路讲透中间会把 next 数组的几种计算方法、教材写法与工程写法的差异、以及我调模板时踩过的坑一并交代清楚适合算法入门、竞赛选手和面试前突击三类人看。1.1 前缀函数的定义排除“平凡自匹配”的那一刻开始前缀函数针对字符串的每个前缀求一个长度对于 s 的前缀 s[0..i]找一个最大的 k要求 s[0..k-1]长度为 k 的前缀恰好等于 s[i-k1..i]长度为 k 的后缀并且 k 不能取 i1。为什么必须排除整个串自身因为任何一个前缀的前缀和后缀都等于它自己如果允许 k i1那么所有 pi[i] 都直接等于 i1数组就完全失去信息量。我们关心的是“真正能复用的重叠部分”所以必须限定真前、后缀。这个定义对应教材里的一个词border。border 就是“既是真前缀又是真后缀”的子串。前缀函数 pi[i] 就是在说s[0..i] 的最长 border 长度是多少。理解成“回退地图”更好懂你已经匹配到第 i 位这个值告诉你在已匹配的部分里最长能保留多少字符继续和接下来的文本对齐不用从头再来。1.2 手工算一遍 pi比背十遍公式都管用以经典例子 s ababaca 手动推一遍i前缀 s[0..i]最长相等真前后缀pi[i]0a无01ab无02abaa13ababab24ababaaba35ababac无06ababacaa1所以 pi {0, 0, 1, 2, 3, 0, 1}。光看数字很抽象但换成场景就清楚了假设模式串匹配文本到第 4 位说明已经匹配出 ababa这个前缀里 aba 既是头又是尾失配时模式串整体向右滑等于只丢掉 ab 两个字符“aba” 这段仍然对齐着直接从那之后继续比较。这就是 KMP 比暴力快的原因——它从不回头重复比较已经确认相等的字符。2. 线性求前缀函数回退链如何做到均摊 O(n)2.1 核心递推border 的 border 还是 border暴力求 pi 是从大到小枚举 k 逐个验证最坏 O(n^2)等于白搭。线性方法的思路是站在之前的结果上往后推。设 pi[i-1] j说明 s[0..j-1] 是 s[0..i-1] 的最长 border。现在考虑新字符 s[i]如果 s[i] 恰好等于 s[j]那可以直接“延长”这个 border得到 pi[i] j 1。如果不相等我们需要在更短的 border 里找机会。这里的关键问题是下一个候选长度去哪找答案是 pi[j-1]。原理是一个漂亮的传递性质border 的 border仍然是原字符串的 border。s[0..j-1] 是 s[0..i-1] 的 border那么 s[0..j-1] 的 border长度 pi[j-1]既是 s[0..j-1] 的前缀又是它的后缀而后缀部分又接在 s[0..i-1] 的后缀里于是它同时是整段前缀的前缀和后缀——合法候选成立。这个链式回退保证不遗漏任何可能又能让候选长度快速收缩是整套算法的灵魂。2.2 模板代码与复杂度拆解下面这版是我默认在用的0-basedC没有任何多余操作vectorint get_pi(const string p) { int m (int)p.size(); vectorint pi(m, 0); 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; } return pi; }逐行解释pi[0] 固定为 0i 从 1 开始j 先继承上一轮结果while 做链式回退直到 p[i] 能和 p[j] 对上最后 if 判断能不能扩展 1 位。复杂度是均摊 O(m)i 每轮最多让 j 增加 1整个过程中 j 的增量总数不超过 m而 while 每执行一次 j 至少减 1j 又不可能为负所以回退总次数也被 m 限制住。两头一夹总操作数 O(m)。Python 版本逻辑完全一致只是语法换了def get_pi(p: str) - list[int]: pi [0] * len(p) for i in range(1, len(p)): j pi[i - 1] while j and p[i] ! p[j]: j pi[j - 1] if p[i] p[j]: j 1 pi[i] j return pi另外值得记住一点pi 数组只依赖模式串不依赖文本。这决定了 KMP 可以做流式匹配——文本多长都不影响内存只要存模式串的 pi就能一边读文本一边出结果。3. KMP 匹配主流程next 数组的三种写法一次说清3.1 匹配主循环失配时模式串滑到哪建好 pi 之后匹配过程就是把“模式串已匹配长度 j”当作状态。比较 t[i] 和 p[j]相等就 j失配就把 j 退到 pi[j-1]相当于模式串整体右滑让已匹配部分里的最长 border 重新对齐再继续比较。这个回退逻辑和 build 阶段一模一样只是比较对象从模式串自己换成了文本和模式串。vectorint kmp_match(const string t, const string p) { vectorint pos; int m (int)p.size(); if (m 0) return pos; vectorint pi get_pi(p); int j 0; for (int i 0; i (int)t.size(); i) { while (j 0 t[i] ! p[j]) j pi[j - 1]; if (t[i] p[j]) j; if (j m) { pos.push_back(i - m 1); j pi[j - 1]; // 继续找重叠/后续匹配 } } return pos; }匹配成功后不要急着把 j 清零j pi[j-1] 是为了不遗漏重叠出现的情况。比如在 aaaa 里找 aa正确结果是 0、1、2 三个位置如果清零只会得到 0、2 两个。很多新手在这里翻车因为样例里正好没有重叠匹配导致隐患一直藏到大数据才爆出来。3.2 教材 next / nextval 与 pi 的换算关系如果你是从严蔚敏那版教材学的 KMP看到的可能是 1-based 的 next 数组甚至还有 nextval学生时代死记硬背的“next 计算”和现在我们写的 0-based pi 对不上很正常。先把结论摆出来教材的 next[1] 0对于 i ≥ 2next[i] 前 i-1 个字符组成的前缀的最长相等前后缀长度 1。换算成 0-based 的 pinext[i] pi[i-2] 1。用教材常客模式串 abaabcac 验证1-based 的 next {0, 1, 1, 2, 2, 3, 1, 2}0-based 的 pi {0, 0, 1, 1, 2, 0, 1, 0}逐位代进去完全吻合。教材引入 nextval 是为了再跳过一层如果回退后落到的字符恰好和失配字符相同下一次比较必然又失败不如直接继续回退。这个优化在 pi 版本里其实由 while 的链式回退天然吸收了不需要额外数组。经典教材的 next 计算代码注意 P 是 1-basedP[0] 不存内容void get_next(char P[], int m, int next[]) { int i 1, j 0; next[1] 0; while (i m) { if (j 0 || P[i] P[j]) { i; j; next[i] j; } else { j next[j]; } } }我把两种写法整理成一张对照表方便你随时查流派下标核心数组语义失配回退适合场景前缀函数 pi0-basedpi[i] 是最长相等真前后缀长度j pi[j-1]工程与算法题首选教材 next1-basednext[1]0next[i]pi[i-2]1j next[j]教材与考试nextval1-based在 next 基础上继续跳过相同字符j nextval[j]极端重复串我的建议很直接写题和工程里只用 pi 版本它天然避开 1-based 的无数 off-by-one。如果题目或面试故意考教材 next按表格里的换算关系手动推绝不要在代码里混用两套下标。3.3 拼接写法与分隔符之坑除了双指针匹配还有一大流派是“拼接 一次 get_pi”构造 s p sep t然后找 pi[i] m 的位置即匹配终点。代码短记忆成本低但有两个坑必须知道。第一个坑是分隔符。必须选一个绝不出现在 p 和 t 里的字符通常用 # 或 \0作用是切断模式串与文本之间、以及模式串内部跨边界的 border 干扰。只要文本里真的含有这个字符结果就会错乱而且很隐蔽。更稳的做法是不确定字符集就别用拼接法回到双指针如果字符串可能包含任意字节可以把 string 转成 vector 后用 -1 做哨兵。第二个坑是下标换算。拼接后串联串长度为 m 1 |t|pi[i]m 对应的文本起点是 i - 2*m这个“减两个 m”的式子我每次写都要心里过一遍于是干脆把它注释在代码里vectorint kmp_by_concat(const string t, const string p) { vectorint pos; int m (int)p.size(); if (m 0) return pos; string s p; s.push_back(\0); // 哨兵确保不出现 s t; vectorint pi get_pi(s); for (int i m 1; i (int)s.size(); i) if (pi[i] m) pos.push_back(i - 2 * m); // 对应 t 中的起点 return pos; }实测下来我对双指针版的信任度更高因为少一个“字符集不包含哨兵”的前提假设就少一类隐蔽 bug。4. 字符串周期用前缀函数一行判断最小循环节4.1 周期与 border 的一个等式字符串周期是前缀函数的另一个高频落点。字符串 s 的长度为 p 的周期按最常见的定义弱周期是对任意满足 ip n 的 i都有 s[i] s[ip]。通俗讲就是把字符串平移 p 格重叠部分完全一致。而 border 说的是前缀等于后缀。这两个概念实际上是一个等式存在长度为 k 的 border等价于存在周期 n-k。证明很直接设 s[0..k-1] s[n-k..n-1]令 p n-k则对于 i 0..k-1s[i] 恰好等于 s[ip]而 ip 的范围是 p..n-1正好覆盖所有需要验证的位置平移等式成立。反过来也成立有周期 p则长度为 n-p 的前后缀必然相等。所以“找所有周期 找所有 border”而所有 border 就是 pi[n-1] 不断沿 pi 链往前跳得到的序列。4.2 最小循环节判定模板“字符串是否由某个基本单元重复拼接而成”是周期问题最常见的形态力扣 459、POJ 2406 的 Power Strings、HDU 1358 的 Period 都是这类。判断只需要两行逻辑bool is_power_string(const string s) { int n (int)s.size(); vectorint pi get_pi(s); int unit n - pi[n - 1]; return unit n n % unit 0; }unit 就是最小循环节长度。为什么成立时 unit 一定是最小周期因为任何更短的周期都对应更长的 border而 pi[n-1] 已经是整个串的最长真 borderunit n - pi[n-1] 必然是最小弱周期。如果 n % unit 0说明字符串可以被等长切成整数块每块都等于 s[0..unit-1]完美循环成立如果不整除串只是“部分周期”现象。拿 abcab 举例pi[4] 2unit 3但 5 % 3 ! 0所以它有弱周期 3头和尾重合了 ab却不是某个单位的整串重复。这两者有本质区别做题前先看清题目要的是完整循环节还是任意弱周期。4.3 枚举全周期border 链的实际用法如果题目要输出所有可能的周期而不是只判断最小循环节就直接遍历 border 链vectorint all_periods(const string s) { int n (int)s.size(); vectorint pi get_pi(s); vectorint res; int k pi[n - 1]; while (k 0) { res.push_back(n - k); k pi[k - 1]; } res.push_back(n); // 自身也算周期 return res; }拿 abababab 实验n 8pi[7] 6border 链是 6、4、2、0对应周期 2、4、6、8。这说明它既能看成两个 abab 拼接也能看成四个 ab 拼接最小完整循环节是 ab。在一些需要枚举循环节或者检查“是否存在周期 p”的题目里直接拿这个数组做候选集速度和正确性都比哈希写法稳。5. 实战排错与经验备忘几个隐蔽 bug 和一个对拍技巧5.1 五个最容易出错的现场这些年我从自己和别人代码里见过的 KMP bug 高度集中整理成一个速查表症状根因一句解匹配结果少了重叠位置匹配成功后把 j 直接清零改成 j pi[m-1]偶发越界或死循环用 size_t 做下标j 减到 -1长度一律转 int 再算匹配数莫名偏多拼接法的分隔符与字符集冲突换哨兵或改双指针回退结果和预想不符pi[j] 与 pi[j-1] 用混回退永远是对已匹配长度 j 取 pi[j-1]模式串为空或长度为 1 时出怪结果没有单独特判m0 提前返回空长度 1 检查比较逻辑其中“回退用 pi[j-1]”这条最值得强调。你的已匹配长度是 j候选 border 长度当然取 pi[j-1]写成 pi[j] 读的是下一个位置的值既容易越界也可能恰好掩盖错误。无符号下标的问题也常见j 0 时再执行 j pi[j-1] 会把 j 变成极大无符号数轻则越界重则死循环所以我一律用 int 存长度。5.2 调试技巧与“什么时候别用 KMP”我每次写新版本都会顺手写一个十行的暴力对拍随机生成长度 1 到 20 的小写字母串暴力枚举起点统计匹配再和 kmp_match 的结果比对跑一万组。除了随机串固定测这四类边界全相同字符aaaaaa 找 aa、模式串等于文本、模式串比文本长、只有一个字符的文本。这一套能拦住绝大多数 off-by-one也适合新手自测。另一个容易被忽略的事实是KMP 的复杂度很稳但常数不一定比标准库 find 小因为很多平台的 find 做了底层向量化优化。所以别把所有字符串查找都替换成 KMP。什么情况才值得用你写的是算法题、模式串固定、需要严格线性复杂度、或者需要自己拿到所有匹配位置。模式串有多个时优先 AC 自动机而不是 KMP 的变体模式串频繁变化时字符串哈希可能更省事带通配符的匹配KMP 也帮不上忙去想想动态规划或者其他方案。5.3 把这套模板收进自己的工具箱我的做法是把 get_pi 和 kmp_match 两个函数固定存在代码片段里注释写清楚前置条件和注意事项。周期判断和枚举就是一行调用不值得单独记。下次遇到“找子串出现次数”“判断字符串是否循环”“求最小循环节”这类题直接调用把精力留给边界条件和业务逻辑。最后分享一个面试现场的小技巧要手写 KMP 时别从背代码开始先写出 pi 的循环头两行再对着“pi[i-1] 是上一轮最长 border”的语义把 while 补全最后写匹配循环。这个过程比默写整段会慢几秒但能大幅降低下标记错的风险而且向面试官展示你是真懂而不是背模板。毕竟这种基础算法考的不是“能不能跑通”而是“出问题能不能两分钟定位”。这套模板在我手里已经用了很久从竞赛到工程再到给别人讲都是靠 S001 这组函数撑起来的属于越用越稳的那种。
