Home Explore Help
Sign In
wfirstzhang
/
lessons
mirror of https://gitee.com/wfz7789/noip_lessons.git
1
0
Fork 0
Files Issues 0 Wiki
Tree: 52bd18832a
Branches Tags
lessons
/
课程
/
04-KMP与Manacher
/
01-KMP失配边界周期与差分建模.md

01-KMP失配边界周期与差分建模.md 11 KB
History Raw

KMP：失配跳转、Border、周期与差分建模

建议先完成 课前零食：不从头再看的字符串，亲手跟一次 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] 也随之出现。按长度从大到小传播：

occ[pi[i]]++
for len = n ... 1:
    occ[pi[len-1]] += occ[len]
for len = 1 ... n:
    occ[len]++  // 前缀自身那一次

核心知识与实现指南

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
  • 原来源：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|)$。

核心伪代码与参考实现附件

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

复盘与变式

若只问是否出现，可第一次完整匹配后结束；若模式为空，C++ 库有自己的约定，但竞赛题通常排除，不能直接访问 pattern[0]。

精选例题 2：Power Strings

来源信息与题意

  • VJudge：POJ-2406 Power Strings
  • 原来源：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)$。

核心伪代码与参考实现附件

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

复盘与变式

“周期为 $p$”不等于“能切成完整周期块”；例如 abcab 有平移意义的周期 3，却不是同一块的整数次幂。

精选例题 3：Prefixes and Suffixes

来源信息与题意

给长度 $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)$。

核心伪代码与参考实现附件

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

复盘与变式

CodeForces-126B Password 要求最长 border 还在中间出现一次。可沿最终 border 链寻找第一个在前 $n-1$ 个位置中出现的长度；它是本题计数信息的直接筛选版本。

精选例题 4：MUH and Cube Walls

来源信息与题意

有长度 $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 防止以后范围扩展导致溢出。

核心伪代码与参考实现附件

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

复盘与变式

差分消除的是加法平移。若允许整体乘正数，还需比较差分比例并处理零；若允许翻转，需再匹配反向差分。技巧能否使用取决于变换下的不变量。

扩展与联系

  • 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 链章节。