字符串匹配算法工程对比：KMP、Boyer-Moore 与 Rabin-Karp 的适用场景

一、三种算法都能 O(n) 匹配，为什么不同场景用不同的

字符串匹配是算法课上的经典内容。KMP、Boyer-Moore、Rabin-Karp 三种算法在理论上的最坏复杂度都接近 O(n+m)（n 为文本长度，m 为模式串长度）。但如果你去翻 grep 的源码，会发现它用的是 Boyer-Moore 的变种；而如果你写一个简单的文本编辑器搜索功能，可能直接用暴力匹配就够了。

选择哪个算法，答案不在复杂度公式里，而在实际输入的特征和工程约束中。

二、三种算法的核心差异

flowchart TD
    A[字符串匹配问题] --> B{输入特征}
    B -->|模式串较短 / 预处理开销敏感| C[KMP]
    B -->|模式串较长 / 文本较大| D[Boyer-Moore]
    B -->|多模式匹配 / 模糊匹配| E[Rabin-Karp]

    C --> C1[利用前缀函数跳过重复比较]
    D --> D1[从右向左匹配，利用坏字符/好前缀规则跳过大段文本]
    E --> E1[用哈希值快速过滤，部分匹配时才逐字符验证]

三、算法实现与注释

3.1 KMP：利用前缀函数的确定性跳转

def kmp_search(text: str, pattern: str) -> int:
    """KMP 字符串匹配

    核心思想：当匹配失败时，利用已匹配部分的信息，
    决定模式串应该右移多少位，而不是回退文本指针。

    时间复杂度：O(n + m)，其中 n = len(text), m = len(pattern)
    空间复杂度：O(m) 用于存储前缀函数
    """
    if not pattern:
        return 0

    # 第一步：构建前缀函数（prefix function / failure function）
    # pi[i] 表示 pattern[0..i] 的最长相等前后缀长度
    pi = [0] * len(pattern)
    j = 0  # 前缀长度
    for i in range(1, len(pattern)):
        # 不匹配时，回退到上一个可能的前缀位置
        while j > 0 and pattern[i] != pattern[j]:
            j = pi[j - 1]
        if pattern[i] == pattern[j]:
            j += 1
        pi[i] = j

    # 第二步：在文本中匹配
    j = 0  # pattern 中的位置
    for i in range(len(text)):
        while j > 0 and text[i] != pattern[j]:
            j = pi[j - 1]  # 回退 pattern 指针
        if text[i] == pattern[j]:
            j += 1
        if j == len(pattern):
            return i - j + 1  # 匹配成功，返回起始位置

    return -1  # 未找到

3.2 Boyer-Moore：利用文本特征大幅跳跃

def boyer_moore_search(text: str, pattern: str) -> int:
    """Boyer-Moore 字符串匹配（简化版：仅坏字符规则）

    核心思想：
    1. 从右向左匹配（这是和 KMP 最根本的区别）
    2. 匹配失败时，根据坏字符规则计算跳跃距离
    3. 模式串较长时，平均只需比较 n/m 个字符

    为什么快？因为它能跳过的不是"确认匹配的字符"，
    而是"确认不匹配的字符"。在实际文本中，
    大部分字符都是不匹配的，所以能跳过很多。

    时间复杂度：平均 O(n/m)，最坏 O(n×m)
    """
    m = len(pattern)
    n = len(text)
    if m == 0:
        return 0

    # 坏字符表：记录模式串中每个字符最后出现的位置
    # 当匹配失败时，根据坏字符来计算跳跃距离
    bad_char = {}
    for i, ch in enumerate(pattern):
        bad_char[ch] = i

    i = 0  # 文本中当前对齐的起始位置
    while i <= n - m:
        j = m - 1  # 从模式串最右端开始比较

        # 从右向左匹配
        while j >= 0 and pattern[j] == text[i + j]:
            j -= 1

        if j < 0:
            # 全部匹配成功
            return i

        # 坏字符规则：计算跳跃距离
        # 如果 text[i+j] 在模式串中出现过，跳过到出现位置对齐
        # 如果没出现过，整个模式串跳过这个字符
        bad_char_pos = bad_char.get(text[i + j], -1)
        # 跳跃距离至少为 1（避免死循环）
        i += max(1, j - bad_char_pos)

    return -1

3.3 Rabin-Karp：哈希加速的批量匹配

def rabin_karp_search(text: str, pattern: str, prime: int = 101) -> int:
    """Rabin-Karp 字符串匹配

    核心思想：
    1. 计算模式串的哈希值
    2. 滑动窗口计算文本中每个等长子串的哈希值
    3. 哈希匹配时再做逐字符验证（防止哈希碰撞）

    适合场景：
    - 多模式匹配（模式串的哈希值只算一次）
    - 模糊匹配（只需改动哈希函数）
    - 不是最快，但最灵活

    时间复杂度：平均 O(n+m)，最坏 O(n×m)（哈希碰撞时）
    """
    m = len(pattern)
    n = len(text)
    if m == 0:
        return 0
    if m > n:
        return -1

    # 计算模式串的哈希值
    pattern_hash = 0
    text_hash = 0
    # h = prime^(m-1)，用于滚动哈希的快速更新
    h = 1

    # 基数取 256（字符集大小），prime 取大质数减少碰撞
    base = 256

    for i in range(m - 1):
        h = (h * base) % prime

    # 计算初始哈希值
    for i in range(m):
        pattern_hash = (base * pattern_hash + ord(pattern[i])) % prime
        text_hash = (base * text_hash + ord(text[i])) % prime

    # 滑动窗口匹配
    for i in range(n - m + 1):
        if pattern_hash == text_hash:
            # 哈希匹配，进行逐字符验证（防止哈希碰撞）
            if text[i : i + m] == pattern:
                return i

        # 滚动哈希：去掉左边字符，加入右边字符
        if i < n - m:
            text_hash = (
                base * (text_hash - ord(text[i]) * h) + ord(text[i + m])
            ) % prime
            # 处理负数取模
            if text_hash < 0:
                text_hash += prime

    return -1

四、工程选型决策树

def select_matching_algorithm(
    pattern_length: int,
    text_length: int,
    alphabet_size: int,
    is_multi_pattern: bool,
) -> str:
    """
    根据实际场景选择合适的字符串匹配算法

    决策逻辑基于实际 benchmark 数据：
    - KMP 在中文文本（大字符集）下表现优于 BM
      （因为坏字符表在大字符集下的跳跃效率下降）
    - BM 在英文文本（小字符集）下表现优异
    - RK 在多模式匹配时绝对优势（模式串哈希预计算）
    """
    if is_multi_pattern:
        return "Rabin-Karp（多模式匹配场景）"

    if pattern_length <= 5:
        return "暴力匹配（短模式串，KMP 预处理开销不值得）"

    if alphabet_size > 256:
        # 大字符集（如中文、Unicode），Boyer-Moore 的坏字符表效率低
        return "KMP（大字符集，Boyer-Moore 跳跃有限）"

    if pattern_length >= 20 and text_length >= 10000:
        return "Boyer-Moore（长模式串 + 大文本，跳跃优势明显）"

    return "KMP（通用场景，性能稳定）"

五、边界与权衡

5.1 短模式串场景

模式串长度小于 5 时，KMP 的预处理开销（构建前缀函数）可能超过匹配本身的时间。暴力匹配在这种场景下反而最快。

5.2 字符集大小对 BM 的影响

Boyer-Moore 的坏字符表大小 = Σ（字符集大小）。对于 Unicode 字符集（Σ 约 10^5），构建完整的坏字符表开销太大。这就是为什么 grep 在实际实现中用的是 BM 的变种（BMH：Boyer-Moore-Horspool），而非原版 BM。

5.3 RK 的哈希碰撞

哈希碰撞会导致误匹配，需要逐字符验证。如果碰撞频繁，复杂度退化为 O(n×m)。选择大质数和合适的基数可以降低碰撞概率，但不能完全消除。

5.4 多模式匹配的需求

如果需要同时搜索多个模式串（如敏感词过滤），AC 自动机（Aho-Corasick）才是最合适的选择。它本质上是 KMP 在多模式场景下的推广。

六、总结

三种字符串匹配算法的复杂度看起来差不多，但实际表现取决于输入特征。KMP 稳定但不够极致，Boyer-Moore 在长模式串的英文文本中表现优异，Rabin-Karp 的灵活性在多模式场景中无出其右。理解它们的差异，比你背下三种代码更有工程价值。