3.8 字符串匹配

这一节，你能解决什么问题

学完这一节，你能够：

理解三种字符串匹配算法（朴素、Rabin-Karp、KMP）的原理
分析 Rabin-Karp 的滚动哈希——如何用 O(1) 更新哈希值
理解 KMP 失败函数的设计直觉——为什么"前缀同时也是后缀"能让我们跳跃
手动追踪 KMP 的执行过程，理解失败后的跳转逻辑
判断什么时候用哪种匹配算法

问题情境

某搜索团队发现搜索延迟从 200ms 上升到 500ms，用户投诉激增。

排查发现：朴素字符串匹配太慢。

文档库：100 万篇，平均 5000 字符
关键词：平均 5 字符

朴素匹配：5000 × 5 × 100万 = 250 亿比较

太慢！

改用 Rabin-Karp + Bloom Filter 预过滤，延迟降到 50ms。

问题：为什么 Rabin-Karp 更快？KMP 更好在哪里？

直观思路

字符串匹配问题：文本 T（长度 n），模式 P（长度 m），找出所有匹配位置。

朴素方法：逐位置尝试，每次 O(m) 比较 → O(nm)

三种优化思路：

Rabin-Karp：用哈希比较代替逐字符比较
KMP：失败后"跳过"已匹配部分，利用模式串的自结构
Boyer-Moore：从右往左匹配，跳过更多

这个方法是怎么想到的

Rabin-Karp 的思路

问题：逐字符比较太慢。

洞察：哈希比较更快。相等 → 可能匹配 → 验证。

关键：滚动哈希，O(1) 更新。从位置 s 到 s+1，只需要去掉 T[s]，加入 T[s+m]。

KMP 的思路

问题：失败后从头开始，浪费已匹配信息。

场景：

文本：   A B A B A B C ...
模式：   A B A B A C
匹配到： A B A B A | C ← 这里失败

朴素做法：从模式的第一个字符重新开始匹配。

但仔细看：我们已经匹配了 "ABABA"，模式串是 "ABABAC"。

关键洞察：模式串 "ABABAC" 的开头 "AB" 既是前缀，也是已匹配部分 "ABABA" 的后缀！

所以我们可以直接跳到位置 2（"AB" 的长度），而不是从 0 开始。

直觉：模式串可以"记忆"自己的结构——如果某部分既是开头（前缀），也是结尾（后缀），失败后可以直接跳到等价的起始位置。

规范定义

字符串匹配

输入：文本 T（长度 n），模式 P（长度 m）输出：所有 P 在 T 中出现的位置

复杂度对比

算法	预处理	匹配时间	特点
朴素	无	O(nm)	简单
Rabin-Karp	O(m)	O(n) 期望	哈希
KMP	O(m)	O(n)	失败函数，最坏保证

算法实现

Rabin-Karp：滚动哈希

python

def rabin_karp(T, P):
    n, m = len(T), len(P)
    if m > n:
        return -1
    
    # 选择哈希参数
    d = 256      # 字符范围（ASCII）
    q = 101      # 质数，避免溢出
    
    # 预处理：计算模式的哈希，和第一个窗口的哈希
    p_hash = 0
    t_hash = 0
    h = 1  # d^(m-1) mod q，用于滚动
    
    for i in range(m):
        p_hash = (d * p_hash + ord(P[i])) % q
        t_hash = (d * t_hash + ord(T[i])) % q
        if i < m - 1:
            h = (h * d) % q
    
    # 滑动窗口
    for s in range(n - m + 1):
        if p_hash == t_hash:  # 哈希匹配，验证
            if T[s:s+m] == P:
                return s
        
        # 滚动更新哈希（去掉 T[s]，加入 T[s+m]）
        if s < n - m:
            t_hash = (d * (t_hash - ord(T[s]) * h) + ord(T[s+m])) % q
            # 处理负数
            if t_hash < 0:
                t_hash += q
    
    return -1

滚动哈希数学：

把字符串看作 d 进制数：

H = Σ c_i × d^{m-1-i}

从 H(T[s..s+m-1]) 到 H(T[s+1..s+m])：
去掉 T[s] 的贡献，加入 T[s+m]

= (H - T[s] × d^{m-1}) × d + T[s+m]

一步步执行：

T = "ABABCABABAB", P = "ABAB"

预处理：
d = 256, q = 101
h = d^(m-1) mod q = 256^3 mod 101 = 65

p_hash = hash("ABAB")
t_hash = hash("ABAB")（第一个窗口）

位置 s=0：
哈希匹配，验证 T[0:4] = "ABAB" == P → 找到！

滚动到 s=1：
t_hash = (256 × (hash("ABAB") - 'A' × 65) + 'C') mod 101
        = hash("BABC")
不匹配，继续

...

KMP：失败函数

失败函数定义：failure[i] = 最长的既是 P[0..i] 的前缀，也是 P[0..i] 的后缀的长度。

直觉：如果在位置 i+1 匹配失败，我们可以跳到位置 failure[i]，因为前面的 failure[i] 个字符已经匹配了。

为什么？ 因为 P[0..failure[i]-1] 既是模式串的前缀，也是刚匹配部分的后缀！

python

def compute_failure(P):
    m = len(P)
    failure = [0] * m
    
    # failure[0] = 0（单字符没有真前缀后缀）
    
    k = 0  # 当前最长匹配前缀长度
    for i in range(1, m):
        # 如果 P[i] != P[k]，回退到上一个匹配位置
        while k > 0 and P[i] != P[k]:
            k = failure[k - 1]
        
        if P[i] == P[k]:
            k += 1
        
        failure[i] = k
    
    return failure

手动计算例子：P = "ABABAC"

i=0: P[0]="A", failure[0]=0（单字符）

i=1: P[1]="B"
     P[1] != P[0] → k=0
     failure[1]=0

i=2: P[2]="A"
     P[2] == P[0] → k=1
     failure[2]=1
     解释："ABA" 的前缀 "A" = 后缀 "A"

i=3: P[3]="B"
     P[3] == P[1] → k=2
     failure[3]=2
     解释："ABAB" 的前缀 "AB" = 后缀 "AB"

i=4: P[4]="A"
     P[4] == P[2] → k=3
     failure[4]=3
     解释："ABABA" 的前缀 "ABA" = 后缀 "ABA"

i=5: P[5]="C"
     P[5] != P[3] → 回退 k=failure[3]=2
     P[5] != P[2] → 回退 k=failure[2]=1
     P[5] != P[1] → 回退 k=failure[1]=0
     P[5] != P[0] → k=0
     failure[5]=0

结果：failure = [0, 0, 1, 2, 3, 0]

前缀后缀对应关系：

P = "ABABAC"

位置 2: "ABA"
  前缀: "A"
  后缀: "A"
  failure[2] = 1 ✓

位置 3: "ABAB"
  前缀: "AB"
  后缀: "AB"
  failure[3] = 2 ✓

位置 4: "ABABA"
  前缀: "A", "AB", "ABA"
  后缀: "A", "BA", "ABA"
  最长匹配: "ABA"（长度3）
  failure[4] = 3 ✓

KMP 匹配：

python

def kmp(T, P):
    n, m = len(T), len(P)
    failure = compute_failure(P)
    
    j = 0  # 模式位置
    for i in range(n):
        # 不匹配时，跳到失败位置
        while j > 0 and T[i] != P[j]:
            j = failure[j - 1]  # 跳到上一个位置的失败值
        
        if T[i] == P[j]:
            j += 1
        
        if j == m:  # 完全匹配
            return i - m + 1  # 返回起始位置
    
    return -1

手动追踪例子：T = "ABABCABABABABAC"，P = "ABABAC"

failure = [0, 0, 1, 2, 3, 0]

i=0: T[0]="A", P[0]="A" → 匹配，j=1
i=1: T[1]="B", P[1]="B" → 匹配，j=2
i=2: T[2]="A", P[2]="A" → 匹配，j=3
i=3: T[3]="B", P[3]="B" → 匹配，j=4
i=4: T[4]="A", P[4]="A" → 匹配，j=5
i=5: T[5]="C", P[5]="C" → 匹配，j=6 → 找到！位置 = 5-5 = 0

假设中间某处失败：
i=某位置: T[i] != P[j]
j 回退到 failure[j-1]
继续比较 T[i] 和 P[j]

关键：j 回退后，前面 failure[j-1] 个字符已经匹配了！
因为这部分既是前缀，也是已匹配部分的后缀。

为什么跳转有效？

假设我们匹配到 P[0..j-1]，然后在 P[j] 失败。

跳转到 j = failure[j-1]。

此时，P[0..failure[j-1]-1] = P[j-failure[j-1]..j-1]（前缀 = 后缀）

所以 T[i-failure[j-1]..i-1] = P[j-failure[j-1]..j-1] = P[0..failure[j-1]-1]

结论：跳转后，前面 failure[j-1] 个字符已经匹配，不需要重新比较！

正确性分析

Rabin-Karp：蒙特卡罗验证

哈希相等 → 可能匹配（假阳性）→ 验证排除。

假阳性概率 = 1/q（如果 q 是质数）。

为什么哈希相等可能有假阳性？

两个不同的字符串可能有相同的哈希值（哈希碰撞）。

但概率很小（1/q），通过逐字符验证排除。

KMP：失败函数保证

失败函数保证不会漏掉匹配位置。

为什么？

每次跳转，我们只跳过那些不可能匹配的位置。

证明：假设跳过了某个可能匹配的位置 s，则：

s < 当前位置（因为跳过）
但 failure 的定义保证 P[0..failure[j-1]-1] = 后缀
如果 s 是可能的匹配，P[0..s-1] 应该和已匹配部分对齐
这与 failure 的定义矛盾

复杂度分析

Rabin-Karp

预处理：O(m)（计算哈希）

匹配：O(n)（每个位置 O(1) 滚动更新，验证概率低）

期望时间：O(n + m)

注意：如果有大量假阳性，验证成本会增加。

KMP

预处理：O(m)（计算 failure）

匹配：O(n)（每个位置最多跳转几次，但总共不超过 O(n)）

证明：

i 每次增加 1
j 增加或减少
j 增加的总次数 ≤ n（因为 j ≤ m）
j 减少的总次数 ≤ j 增加的总次数 ≤ n

所以总比较次数 ≤ 2n。

最坏时间：O(n + m)

什么时候不该用这个方法

该用朴素的情况

模式很短（m 很小）
匹配很少（不匹配后快速失败）
不想预处理

该用 Rabin-Karp 的情况

多模式匹配（多个哈希同时比较）
可以接受概率性结果
需要快速滑动窗口检测

该用 KMP 的情况

需要最坏保证
模式有重复结构（failure 值大）
单模式匹配

本节小结

解决了什么问题？

快速字符串匹配，O(n) 而不是 O(nm)。

核心方法是什么？

Rabin-Karp：滚动哈希 + 蒙特卡罗验证
KMP：失败函数 + 前缀后缀重叠洞察

为什么正确？

Rabin-Karp：哈希相等概率保证，验证排除假阳性
KMP：失败函数跳过不可能匹配的位置，保留可能匹配的

代价是什么？

Rabin-Karp：预处理 O(m)，假阳性需验证
KMP：预处理 O(m)，需要额外数组

适用场景？

文本检索、多模式匹配、需要最坏保证的单模式匹配。

练习

基本理解

练习 1：T = "ABABCABCABAB"，P = "ABAB"。用 Rabin-Karp 找匹配位置，画出哈希更新过程。

练习 2：P = "ABABAC"。手动计算失败函数，解释每个位置的值。

练习 3：T = "ABABABABAC"，P = "ABABAC"。用 KMP 找匹配，追踪 j 的跳转。

失败函数理解

练习 4：计算以下模式的失败函数：

P = "AAAAA"
P = "ABCDE"
P = "ABABABAB"

解释：为什么第一个 failure 增长快，第二个全是 0，第三个交替？

练习 5：解释为什么 failure[i] ≤ i，且 failure[i] = 0 意味着什么？

错误诊断

练习 6：以下 Rabin-Karp 实现有什么问题？

python

def rk_bug(T, P):
    p_hash = hash(P)
    for s in range(len(T) - len(P) + 1):
        t_hash = hash(T[s:s+len(P)])  # ← 每次重新计算
        if t_hash == p_hash:
            if T[s:s+len(P)] == P:
                return s

分析：为什么这不是 O(n)？

练习 7：以下 failure 计算有什么问题？

python

def failure_bug(P):
    failure = [0] * len(P)
    for i in range(1, len(P)):
        if P[i] == P[0]:        # ← 只和第一个比较
            failure[i] = 1
    return failure

分析：这样计算的 failure 会漏掉什么？

方案比较

练习 8：场景选择。

场景	应该用什么？	理由
单模式匹配，最坏保证
多模式匹配（10个模式）
模式很短（2字符），匹配很少
文本搜索，假阳性可接受

上一节：3.7 哈希与随机化

下一节：3.9 二分查找

3.8 字符串匹配 ​

这一节，你能解决什么问题 ​

问题情境 ​

直观思路 ​

这个方法是怎么想到的 ​

Rabin-Karp 的思路 ​

KMP 的思路 ​

规范定义 ​

字符串匹配 ​

复杂度对比 ​

算法实现 ​

Rabin-Karp：滚动哈希 ​

KMP：失败函数 ​

正确性分析 ​

Rabin-Karp：蒙特卡罗验证 ​

KMP：失败函数保证 ​

复杂度分析 ​

Rabin-Karp ​

KMP ​

什么时候不该用这个方法 ​

该用朴素的情况 ​

该用 Rabin-Karp 的情况 ​

该用 KMP 的情况 ​

本节小结 ​

练习 ​

基本理解 ​

失败函数理解 ​

错误诊断 ​

方案比较 ​

3.8 字符串匹配

这一节，你能解决什么问题

问题情境

直观思路

这个方法是怎么想到的

Rabin-Karp 的思路

KMP 的思路

规范定义

字符串匹配

复杂度对比

算法实现

Rabin-Karp：滚动哈希

KMP：失败函数

正确性分析

Rabin-Karp：蒙特卡罗验证

KMP：失败函数保证

复杂度分析

Rabin-Karp

KMP

什么时候不该用这个方法

该用朴素的情况

该用 Rabin-Karp 的情况

该用 KMP 的情况

本节小结

练习

基本理解

失败函数理解

错误诊断

方案比较