字符串匹配算法：KMP 与 BM 算法的原理与 Python 实现

字符串匹配是计算机科学中的核心问题，广泛应用于文本搜索、数据分析和生物信息学等领域。给定一个文本串 $T$ 和一个模式串 $P$，目标是在 $T$ 中快速定位 $P$ 的出现位置。朴素匹配算法（逐个字符比较）的时间复杂度为 $O(nm)$（$n$ 和 $m$ 分别为文本和模式长度），在大型文本中可能较慢。本文将介绍两种改进算法：KMP（Knuth-Morris-Pratt）和 BM（Boyer-Moore），并逐步解释其原理和 Python 实现。文章结构清晰，确保读者能逐步掌握。

1. KMP 算法原理

KMP 算法由 Knuth、Morris 和 Pratt 于 1977 年提出，核心思想是利用已匹配信息避免不必要的回溯。它通过构建“部分匹配表”（又称前缀函数 $\pi$）来跳过无效比较。

• 部分匹配表定义：
  对于模式串 $P$，$\pi[i]$ 表示子串 $P[0..i]$ 的最长真前缀（同时也是后缀）的长度。例如，若 $P = $"ABABC"，则：

  • $\pi[0] = 0$（单字符无真前缀）
  • $\pi[1] = 0$（"AB" 无共同前后缀）
  • $\pi[2] = 1$（"ABA" 的最长前后缀为 "A"，长度 1）
  • $\pi[3] = 2$（"ABAB" 的最长前后缀为 "AB"，长度 2） 数学上，$\pi[i]$ 满足： $$ \pi[i] = \max { k \mid 0 \leq k < i, P[0..k-1] = P[i-k..i-1] } $$ 其中 $k$ 为长度。

• 算法过程：

  1. 预处理：计算 $\pi$ 表。
  2. 搜索：从文本 $T$ 的起始位置开始比较：
     • 若字符匹配，则继续比较下一个。
     • 若不匹配，则根据 $\pi$ 表跳过 $\pi[j]$ 个位置（$j$ 为模式当前索引），避免回溯。 时间复杂度为 $O(n + m)$，空间复杂度为 $O(m)$。

2. KMP 算法的 Python 实现

以下代码实现了 KMP 搜索函数，包括 $\pi$ 表构建和匹配过程：

def kmp_search(text, pattern):
    if not pattern:
        return 0  # 空模式直接返回
    
    # 构建部分匹配表 π
    pi = [0] * len(pattern)
    length = 0  # 当前最长前后缀长度
    i = 1
    while i < len(pattern):
        if pattern[i] == pattern[length]:
            length += 1
            pi[i] = length
            i += 1
        else:
            if length != 0:
                length = pi[length - 1]
            else:
                pi[i] = 0
                i += 1
    
    # 在文本中搜索模式
    i, j = 0, 0  # i: 文本索引, j: 模式索引
    while i < len(text):
        if pattern[j] == text[i]:
            i += 1
            j += 1
            if j == len(pattern):
                return i - j  # 返回匹配起始位置
        else:
            if j != 0:
                j = pi[j - 1]  # 跳过无效比较
            else:
                i += 1
    return -1  # 未找到

# 示例用法
text = "ABABDABACDABABCABAB"
pattern = "ABABC"
print(kmp_search(text, pattern))  # 输出匹配位置

3. BM 算法原理

BM 算法由 Boyer 和 Moore 于 1977 年提出，采用从右向左比较策略，利用“坏字符规则”和“好后缀规则”跳过更多位置。

• 坏字符规则：
  当字符不匹配时，基于文本中的不匹配字符（称为“坏字符”）在模式中的位置计算偏移量。定义坏字符表 $bc$，其中 $bc[c]$ 为字符 $c$ 在模式中最后出现的位置（若未出现，则为 $-1$）。偏移量公式为： $$ \text{shift} = j - bc[T[i+j]] $$ 其中 $j$ 是模式索引，$i$ 是文本偏移。

• 好后缀规则：
  当部分后缀匹配时，基于已匹配的后缀计算偏移量。定义好后缀表 $gs$，其中 $gs[k]$ 表示当后缀长度 $k$ 匹配时，模式可跳过的位置。偏移量基于最长匹配后缀。

• 算法过程：

  1. 预处理：构建 $bc$ 和 $gs$ 表。
  2. 搜索：从模式末尾开始比较文本：
     • 若字符匹配，则向左移动。
     • 若不匹配，则计算坏字符和好后缀的偏移量，取最大值跳过。 最坏时间复杂度为 $O(nm)$，但实际中常优于 KMP，尤其当模式较长时。

4. BM 算法的 Python 实现

以下代码实现了 BM 搜索函数，包括规则表构建和匹配过程：

def bad_char_heuristic(pattern):
    bad_char = {}
    for i, char in enumerate(pattern):
        bad_char[char] = i  # 记录字符最后出现位置
    return bad_char

def good_suffix_heuristic(pattern):
    m = len(pattern)
    good_suffix = [-1] * (m + 1)  # 初始化表
    
    # 计算后缀数组
    suffix = [-1] * (m + 1)
    for i in range(m):
        j = m - 1
        k = i
        while k >= 0 and pattern[k] == pattern[j]:
            k -= 1
            j -= 1
        if k < 0:
            suffix[i + 1] = j + 1
        else:
            suffix[i + 1] = suffix[i]
    
    # 构建好后缀表
    for i in range(m + 1):
        if suffix[i] == -1:
            good_suffix[i] = m - i
        else:
            good_suffix[i] = m - suffix[i]
    return good_suffix

def bm_search(text, pattern):
    if not pattern:
        return 0
    
    n, m = len(text), len(pattern)
    bad_char = bad_char_heuristic(pattern)
    good_suffix = good_suffix_heuristic(pattern)
    
    s = 0  # 文本偏移量
    while s <= n - m:
        j = m - 1  # 从模式末尾开始比较
        while j >= 0 and pattern[j] == text[s + j]:
            j -= 1
        if j < 0:
            return s  # 匹配成功
        else:
            # 坏字符规则偏移
            char = text[s + j]
            bc_shift = j - bad_char.get(char, -1)
            # 好后缀规则偏移
            gs_shift = good_suffix[j + 1]
            s += max(bc_shift, gs_shift)  # 取最大偏移
    return -1  # 未找到

# 示例用法
text = "HERE IS A SIMPLE EXAMPLE"
pattern = "EXAMPLE"
print(bm_search(text, pattern))  # 输出匹配位置

5. 算法比较

• KMP：优势在于模式重复度高时表现稳定，时间复杂度 $O(n + m)$ 有保障。但预处理稍复杂。
• BM：优势在于实际匹配中跳过位置多，尤其适合长模式。但最坏情况可能较慢。
• 一般建议：BM 在随机文本中更快，KMP 在模式有重复子串时更优。

6. 结论

KMP 和 BM 算法通过智能跳过无效比较，显著提升了字符串匹配速度。本文详细解释了原理，并提供了 Python 实现代码。读者可结合示例测试，加深理解。掌握这些算法能优化文本处理应用，如搜索引擎和数据分析工具。实践中，建议根据数据特性选择合适算法。