S03-X10 · 字符串匹配：KMP 与滚动哈希

朴素匹配三行代码，绝大多数输入也确实够快——所以很多人一辈子没写对过 KMP，却一直在用 indexOf。真正需要专门算法的只有两种情况：在长文本里反复查同一个模式，或比较任意两个子串是否相等。KMP 管"一次扫描、主串指针不回退"，滚动哈希管"O(1) 取任意子串指纹"，选错不报错，只会慢。

1. 朴素匹配为什么慢

def naive_search(text: str, pat: str) -> int:
    n, m = len(text), len(pat)
    for i in range(n - m + 1):
        j = 0
        while j < m and text[i + j] == pat[j]:
            j += 1
        if j == m:
            return i
    return -1

失配时 i 只前进 1，把已经确认过的信息全丢掉重来。最坏输入是"几乎全匹配、最后一位失败"：

输入	每次比较	总量级
`"aaaa…a"` 配 `"aaa…ab"`	m − 1 或 m	约 (n−m)·m
随机文本 + 短模式	1–2 次就失配	接近 O(n)
DNA / 重复日志	高度重复	接近 O(n·m)

"典型量级"很关键：随机英文文本里朴素匹配平均就是 O(n)，退化只发生在周期性强的输入上。要不要上 KMP，看输入是否有周期性，不看 n 有多大。

2. pi 数组：含义与构造

pi[i] 的定义：pat[0..i] 里最长的"既是前缀又是后缀"的真前缀长度（不含整段自身）。

以 pat = "ababaca" 为例：

i	0	1	2	3	4	5	6
`pat[i]`	a	b	a	b	a	c	a
`pi[i]`	0	0	1	2	3	0	1
对应的前后缀	—	—	`a`	`ab`	`aba`	—	`a`

pi[4] = 3 读作：ababa 的长 3 前缀 aba 等于长 3 后缀 aba。它的全部用途是失配时告诉你"模式该右移到哪，才能让已匹配的那段后缀继续被利用"。

def build_pi(pat: str) -> list[int]:
    m = len(pat)
    pi = [0] * m
    k = 0                                  # k = 当前已匹配的前缀长度
    for i in range(1, m):
        while k > 0 and pat[i] != pat[k]:
            k = pi[k - 1]                  # 失配：沿 pi 链回退，不是 k -= 1
        if pat[i] == pat[k]:
            k += 1
        pi[i] = k
    return pi

k = pi[k - 1] 是全部难点：它表示"退到次长的相等前后缀"，写成 k -= 1 就错了（会丢掉更短的可行匹配）。构造是 O(m)：k 的增量总和受 i 约束，while 的总回退次数不超过增量总和。

3. 用 KMP 匹配主串

def kmp_search(text: str, pat: str) -> int:
    m = len(pat)
    if m == 0:
        return 0
    pi = build_pi(pat)
    k = 0
    for i, ch in enumerate(text):
        while k > 0 and ch != pat[k]:
            k = pi[k - 1]                  # 主串指针 i 不动
        if ch == pat[k]:
            k += 1
        if k == m:
            return i - m + 1
    return -1

关键点：i 单调递增、永不回退，所有回退都发生在 k 上，文本只被扫一遍，总代价 O(n + m)。KMP 的真正优势不是更快，而是文本流只能读一次（网络流、管道）时不可替代。

两个下标约定混用必错：

约定	`pi` 长度	`pi[i]` 含义	失配时跳到
从 0 开始（本文）	m	`pat[0..i]` 的最长相等前后缀	`pi[k-1]`，k 是已匹配长度
从 1 开始（教材常见）	m+1	`pat[1..i]` 的最长相等前后缀	`pi[k]`

从 1 开始那版 pi[1] = 0 是哨兵、pi 整体右移一位，"跳 pi[k]"与"跳 pi[k-1]"等价。看 pi 的初始化长度即可判断版本。

4. 最小循环节

一个长度为 n 的串，若 n - pi[n-1] 能整除 n，则最小循环节长度就是 n - pi[n-1]。

def min_period(s: str) -> int:
    n = len(s)
    if n == 0:
        return 0
    p = n - build_pi(s)[n - 1]            # 候选循环节长度
    return p if n % p == 0 else n         # 不整除 → 整串才是自己的最小循环节

验证："abcabcabc" 的 pi[-1] = 6，9 - 6 = 3，9 % 3 == 0 → 循环节 "abc"；"ababaca" 的 pi[-1] = 1，7 - 1 = 6，7 % 6 ≠ 0 → 整串。取模判断不能省，否则 "abababx" 会被误判成周期串。

5. 滚动哈希：多项式指纹与增量更新

把字符串视为 base 进制数 h(s) = s[0]·B^(m-1) + … + s[m-1]，再对模数取余。窗口右移只需两步：

MOD = (1 << 61) - 1
BASE = 911382323

def rolling_hash_search(text: str, pat: str) -> int:
    n, m = len(text), len(pat)
    if m > n:
        return -1
    pw = pow(BASE, m - 1, MOD)             # B^(m-1)：窗口最高位的权重
    def h(s):
        v = 0
        for ch in s:
            v = (v * BASE + ord(ch)) % MOD
        return v
    hp, ht = h(pat), h(text[:m])
    if ht == hp and text[:m] == pat:       # 命中必须复核
        return 0
    for i in range(m, n):
        ht = ((ht - ord(text[i - m]) * pw) % MOD * BASE + ord(text[i])) % MOD
        if ht == hp and text[i - m + 1:i + 1] == pat:
            return i - m + 1
    return -1

增量更新的本质是把移出窗口的字符按原权重减掉，再让新字符乘 base 加进来。pw 必须预计算，否则每次移窗都重新求幂，省下的 O(m) 又赔回去。Python 整数不溢出，直接用 2^61 − 1 这类梅森素数模数；Java/C++ 里 int 乘法会溢出，用 long + 1e9+7，或 long 自然溢出（等于模 2^64，底数必须取奇数）。

6. 冲突处理：单模数会被打穿

哈希值相等不代表串相等。工程上三种处理，强度递增：

方案	冲突概率量级	代价	适用
单模数 `1e9+7`	按生日界估算，约 1/MOD 的平方级	最低	非对抗输入、单次查询
双模数（`1e9+7` + `1e9+9`）	两者乘积级	常数约 2 倍	竞赛、需要稳妥的判重
随机底数 + 随机模数	攻击者无法预先构造	同单模数	输入可能来自外部（用户提交、对拍数据）
哈希 + 命中后逐字符复核	冲突不产生错误结果	最坏退化 O(nm)	生产代码的唯一正确做法

两个必须记住的事实：

固定底数 + 固定模数能被构造出全冲突。知道 BASE 与 MOD 就能造出大量同哈希的串，所以对外部输入必须随机化底数，或只把哈希当"过滤器"、命中后做真实比较。
不取模不是"更安全"。long 自然溢出等于模 2^64，底数取偶数时低位信息会成片丢失。

需要"比较任意两个子串"时哈希才有决定性优势——前缀哈希让任意区间指纹变成 O(1)：

def prefix_hash(s):
    h = [0] * (len(s) + 1)
    for i, ch in enumerate(s):
        h[i + 1] = (h[i] * BASE + ord(ch)) % MOD
    return h

def sub_hash(h, l, r, pw):                 # s[l:r] 的指纹，pw 为 BASE 的幂表
    return (h[r] - h[l] * pw[r - l]) % MOD

判断回文、比较两段是否相同这类"多次任意区间查询"，KMP 做不了，哈希是一行。

7. Z 函数、AC 自动机与选型

Z 函数与 KMP 是同一件事的两种记账：z[i] 是 s 与 s[i:] 的最长公共前缀长度。拼 pat + '\0' + text 求 Z，z[i] == len(pat) 处就是匹配点。

def z_function(s: str) -> list[int]:
    n = len(s)
    z = [0] * n
    l = r = 0
    for i in range(1, n):
        if i < r:
            z[i] = min(r - i, z[i - l])    # 借用已算过的区间
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1
        if i + z[i] > r:
            l, r = i, i + z[i]
    return z

min(r - i, z[i - l]) 是 Z 函数的精华，也是与 KMP 的对应点：两者都复用"已比较过的相等关系"，只是 KMP 记模式的 border，Z 记整串的前缀匹配。

需求	选哪个	理由
单模式、文本只能扫一次	KMP	主串指针不回退
多模式同时匹配	AC 自动机	一次扫描命中所有模式
可随机访问、要代码短	朴素或 `str.find`	平均 O(n)，维护成本最低
比较任意子串、判回文、判重	前缀哈希	O(1) 取指纹，KMP 做不到
求最小循环节、border 结构	KMP 的 `pi`	`pi` 直接编码了 border 链

AC 自动机把 KMP 的"失配跳转"推广到 Trie 上，fail 指针就是 pi 在树上的版本。它解决"几千个关键词扫一遍文本"，不是"一个模式扫一遍文本"；只有一两个模式时上 AC 是纯过度设计。

8. 排错：六种"跑通但搜错"

现象	原因	处理
匹配位置全部偏移 1	`pi` 从 1 开始与从 0 开始的约定混用	只看 `pi` 初始化长度判断版本，全文统一
KMP 比朴素还慢	`while` 写成 `k -= 1`，退化成 O(n·m)	回退必须走 `pi[k-1]`
哈希偶尔给错位置	单模数冲突且没复核	命中后必须 `text[l:r] == pat`
换一批数据哈希全撞	底数与模数固定，被构造	随机底数或改双模数
大整数下哈希变慢	没取模，位数持续增长	每步 `% MOD`，模数控制在机器字内
`find` 在特定输入上退化	内置实现的最坏情况没测过	周期性输入要单独构造用例，或换 KMP

最后一条最容易漏：内置实现并不是 KMP——Java 的 String.indexOf 是逐位比较加首字符加速，最坏仍是 O(n·m)；CPython 的 str.find 用 two-way 算法，最坏线性。把内置方法当 KMP 用，等于赌"输入不会周期性重复"。

9. 边界：什么情况本来就该换思路

场景	更好的做法	原因
模式很多、文本很大	AC 自动机	单模式算法要跑 k 遍
需要"文本里任意子串出现几次"	后缀数组 / 后缀自动机	哈希只能判等，答不了计数
近似匹配（允许 k 个错）	编辑距离 DP / 位并行	KMP 没有容错概念
输入随机、模式短	朴素 + 首字符过滤	常数更小，代码更少
判定两个超长文件是否相同	哈希（必要时双向）	逐字节比较的 I/O 成本更高

"防篡改"与"防冲突"是两件事：多项式哈希只保证"随机输入下冲突概率低"，抗不住故意构造；要抗对抗就上 SHA-256，慢一到两个数量级。

10. 自测

朴素匹配在什么形状的输入上退化到 O(n·m)？随机文本为何接近 O(n)？
pi[i] 的准确定义是什么？为什么失配时是 k = pi[k-1] 而不是 k -= 1？
pi 数组从 1 开始的那版，失配跳转写成了 pi[k]，两版为什么等价？
用 n - pi[n-1] 求最小循环节，为什么必须再判一次整除？
滚动哈希的窗口右移，为什么必须先减去"移出字符乘 B^(m-1)"？
什么场景下哈希强于 KMP？什么场景下两者都该换 AC 自动机？