# KMP：失配跳转、Border、周期与差分建模 ## 本节目标 学完后，你应能从朴素匹配推导前缀函数（prefix function），解释失配为何跳到 `pi[j-1]`，并用 border 链解决重叠匹配、周期、前后缀统计及平移不变序列匹配。 ## 前置知识与课前自测 前置：字符串下标、前缀/后缀、基础复杂度。 1. 模式 `AAAA` 在文本 `AAAAA` 中出现几次？匹配成功后把状态清零会漏掉什么？ 2. 字符串的 border 是否允许等于字符串本身？ 3. 若长度 $n$ 字符串有长度 $b$ 的 border，$n-b$ 一定是完整重复周期吗？
自测答案 1. 两次；清零会漏掉从第二个字符开始的重叠出现。 2. 通常 border 指相等的**真**前缀与真后缀，不含自身；题目若另有定义需服从题面。 3. 不一定。$n-b$ 是周期候选，只有整除 $n$ 时才构成若干个完整相同块。
## 问题动机：朴素回退为何浪费 朴素匹配在模式第 $j$ 位失配后，把起点右移一位并重新比较此前已经相等的字符。已知的相等区间其实告诉我们：新候选只能是“模式已匹配前缀的某个 border”。 令 `pi[i]` 为 `s[0..i]` 的最长 border 长度。计算 `pi[i]` 时，先尝试延长 `pi[i-1]`；若新字符失配，把候选长度 $j$ 改为 `pi[j-1]`，沿 border 链继续。每次回退都严格减小 $j$，每次成功延长至多增加 1，整个过程摊还 $O(n)$。 ## 步步式引导 ### 1. 为什么跳到 `pi[j-1]` 已经匹配的长度为 $j$。若新字符不同，任何仍可能接在当前位置之前的模式前缀，必须同时是 `pattern[0..j-1]` 的后缀；最长这样的真前后缀长度正是 `pi[j-1]`。跳得更长没有依据，逐个跳更短又重复工作。 ### 2. 前缀函数不只是匹配器 从长度 $n$ 开始反复令 `x=pi[x-1]`，会枚举全部 border 长度。最长 border $b$ 给出最短周期候选 $p=n-b$；若 `n%p==0`，字符串由长度 $p$ 的块重复。 ### 3. 怎样统计每个前缀出现次数 每个位置 $i$ 首先贡献一次长度 `pi[i]` 的匹配结尾。若长度 $x$ 的前缀出现一次，它的 border `pi[x-1]` 也随之出现。按长度从大到小传播： ```text occ[pi[i]]++ for len = n ... 1: occ[pi[len-1]] += occ[len] for len = 1 ... n: occ[len]++ // 前缀自身那一次 ``` ## 核心知识与实现指南 ```text pi = [0] * len(s) for i in range(1, len(s)): candidate = pi[i - 1] while candidate > 0 and s[i] != s[candidate]: candidate = pi[candidate - 1] if s[i] == s[candidate]: candidate += 1 pi[i] = candidate ``` 循环不变量：进入位置 $i$ 时，$j$ 始终是 `s[0..i-1]` 的某个 border 长度；成功比较后得到 `s[0..i]` 的 border。失败链枚举了全部可能候选，因此不会漏掉更长可行解。总时间 $O(n)$，空间 $O(n)$。 ## 精选例题 1：Oulipo ### 来源信息与题意 - VJudge：[POJ-3461 Oulipo](https://vjudge.net/problem/POJ-3461) - 原来源：BAPC 2006 Qualification - 大致难度：KMP 建模；考点：重叠出现计数 多组数据，模式 $W$ 长 $1..10^4$，文本 $T$ 长至 $10^6$，均为大写字母。统计 $W$ 在 $T$ 中出现次数，允许重叠。
Hint 1对模式计算 `pi`，扫描文本时让 `j` 表示当前匹配前缀长度。
Hint 2失配时沿 `pi[j-1]` 回退，而不是移动文本指针。
Hint 3完整匹配后计数，并令 `j=pi[j-1]` 保留可重叠后缀。
### Observations、Editorial 与证明 文本字符只前进一次，模式状态沿失败链回退。状态 $j$ 始终表示“当前文本前缀的最长后缀与模式前缀相等”的长度；达到 $|W|$ 就得到一次出现。回到最长真 border 后继续，恰保留所有可重叠候选。时间 $O(|W|+|T|)$，空间 $O(|W|)$。 ### 核心伪代码与参考实现附件 ```text pi = prefix_function(pattern) matched = answer = 0 for c in text: while matched > 0 and c != pattern[matched]: matched = pi[matched-1] if c == pattern[matched]: matched += 1 if matched == len(pattern): answer += 1; matched = pi[matched-1] ``` 完整 GNU C++17 参考实现见附件：[POJ-3461.cpp](../../参考实现/04-KMP与Manacher/POJ-3461.cpp) ### 复盘与变式 若只问是否出现，可第一次完整匹配后结束；若模式为空，C++ 库有自己的约定，但竞赛题通常排除，不能直接访问 `pattern[0]`。 ## 精选例题 2：Power Strings ### 来源信息与题意 - VJudge：[POJ-2406 Power Strings](https://vjudge.net/problem/POJ-2406) - 原来源：Waterloo local 2002.07.01 - 大致难度：提高入门；考点：border 与最短周期 每行一个长度不超过 $10^6$ 的字符串，`.` 结束。求最大 $k$，使字符串等于某个非空串重复 $k$ 次。
Hint 1最长 border 长度为 `pi[n-1]`，候选周期是 `n-pi[n-1]`。
Hint 2候选周期必须整除总长度，否则最后只是截断重复，答案为 1。
### Editorial 与证明 令 $p=n-\pi[n-1]$，记 $b=\pi[n-1]=n-p$。border 条件给出 $s[0..b-1]=s[p..n-1]$，即对 $i\in[0,b)$（即 $i\in[0,n-p)$）都有 $s[i]=s[i+p]$；改写下标 $i\to i-p$，等价于对所有 $i\in[p,n)$ 都有 $s[i]=s[i-p]$，因此 $p$ 是周期。若 $p\mid n$，字符串由 $n/p$ 个相同块组成。最长 border 给出最小正周期，因此重复次数最大。若不整除，不存在完整分块重复，答案为 1。复杂度 $O(n)$。 ### 核心伪代码与参考实现附件 ```text pi = prefix_function(s) period = len(s) - pi[-1] if len(s) is divisible by period: output len(s) / period else: output 1 ``` 完整 GNU C++17 参考实现见附件：[POJ-2406.cpp](../../参考实现/04-KMP与Manacher/POJ-2406.cpp) ### 复盘与变式 “周期为 $p$”不等于“能切成完整周期块”；例如 `abcab` 有平移意义的周期 3，却不是同一块的整数次幂。 ## 精选例题 3：Prefixes and Suffixes ### 来源信息与题意 - VJudge：[CodeForces-432D Prefixes and Suffixes](https://vjudge.net/problem/CodeForces-432D) - 原题：[Codeforces Round 246 (Div. 2)](https://codeforces.com/problemset/problem/432/D) - 难度：2000；考点：border 链、前缀出现次数传播 给长度 $1..10^5$ 的大写串。输出所有同时是前缀和后缀的长度，以及该前缀在全串中作为子串出现的次数；长度递增。
Hint 1所有 border 长度由 `n, pi[n-1], pi[pi[n-1]-1], ...` 得到。
Hint 2`pi[i]=x` 表示以 $i$ 结尾有一个长度 $x$ 的前缀出现，但它也同时贡献给 $x$ 的所有 border。
Hint 3按长度从大到小把 `occ[len]` 加到 `occ[pi[len-1]]`。
### Observations、Editorial 与证明 先统计每个 `pi[i]` 作为最长匹配结尾的次数，再沿失败树父边由长到短汇总，最后为每个前缀加入其在开头的自出现。border 链给出需要输出的长度，反转后递增。 每个前缀出现的最长匹配状态位于失败树某个节点；向祖先传播恰把它计入所有较短 border，既不漏也不重。复杂度 $O(n)$。 ### 核心伪代码与参考实现附件 ```text pi = prefix_function(s) occ[pi[i]] += 1 for every position i for length from n down to 1: occ[pi[length-1]] += occ[length] occ[length] += 1 for each prefix's occurrence at position 0 borders = n, pi[n-1], pi[pi[n-1]-1], ... output reversed(borders) with occ[length] ``` 完整 GNU C++17 参考实现见附件：[CodeForces-432D.cpp](../../参考实现/04-KMP与Manacher/CodeForces-432D.cpp) ### 复盘与变式 `CodeForces-126B Password` 要求最长 border 还在中间出现一次。可沿最终 border 链寻找第一个在前 $n-1$ 个位置中出现的长度；它是本题计数信息的直接筛选版本。 ## 精选例题 4：MUH and Cube Walls ### 来源信息与题意 - VJudge：[CodeForces-471D MUH and Cube Walls](https://vjudge.net/problem/CodeForces-471D) - 原题：[Codeforces Round 269 (Div. 2)](https://codeforces.com/problemset/problem/471/D) - 难度：1800；考点：差分消去平移、数列 KMP 有长度 $n$ 的墙高数组 $a$ 与长度 $w$ 的目标墙 $b$，均不超过 $2\times10^5$，高度至 $10^9$。目标墙可整体升降，求它能与 $a$ 的多少个连续长度 $w$ 段重合。
Hint 1整体加同一个常数会改变绝对高度，但不会改变相邻差。
Hint 2当 $w=1$ 时没有差分约束，每个位置都可匹配。
Hint 3在 `diff(a)` 中统计 `diff(b)` 的出现次数，匹配器可直接用于 `long long` 数组。
### Observations、Editorial 与证明 两个等长序列相差统一常数，当且仅当它们的相邻差分完全相等。因此把 $a,b$ 分别差分，在前者中 KMP 匹配后者。每个差分匹配对应唯一一个原数组起点，反之亦然。$w=1$ 时答案为 $n$。复杂度 $O(n+w)$，差分使用 `long long` 防止以后范围扩展导致溢出。 ### 核心伪代码与参考实现附件 ```text if target length == 1: output source length text = adjacent_differences(source_heights) pattern = adjacent_differences(target_heights) output KMP_occurrence_count(pattern, text) ``` 完整 GNU C++17 参考实现见附件：[CodeForces-471D.cpp](../../参考实现/04-KMP与Manacher/CodeForces-471D.cpp) ### 复盘与变式 差分消除的是加法平移。若允许整体乘正数，还需比较差分比例并处理零；若允许翻转，需再匹配反向差分。技巧能否使用取决于变换下的不变量。 ## 扩展与联系 - KMP 自动机把每个状态对每个字符的转移预处理，可用于 DP 统计避免/包含某模式的字符串数。 - Z-function 也能处理前缀匹配与 border；KMP 的失败树更适合出现次数向祖先传播。 - 多模式匹配应考虑 Aho–Corasick；把每个模式单独 KMP 可能达到模式数乘文本长。 ## 总结与自检 1. 失配跳到 `pi[j-1]` 的充要候选依据是什么？ 2. 完整匹配后为何不能把 `matched` 清零？ 3. 最长 border 如何给出最短周期候选？为什么还要整除？ 4. 出现次数为何要在失败树上从长到短传播？ 5. 差分匹配消除了哪一种自由度？ ## 课后训练建议 先不看模板独立写 `prefix_function` 并用朴素 border 对拍。`Oulipo` 与 `Power Strings` 应独立完成；`Prefixes and Suffixes` 重点画失败树；`MUH and Cube Walls` 先证明差分条件充要。完成后再做 `CodeForces-126B`，只在卡住时回看 border 链章节。