高效字符串搜索利器：BM算法详解（Python语言BM算法实现从零开始）

什么是BM算法？

Boyer-Moore算法由Robert S. Boyer和J Strother Moore于1977年提出，是一种从右向左进行模式串匹配的算法。与朴素的暴力匹配不同，BM算法通过两种启发式规则——坏字符规则（Bad Character Rule）和好后缀规则（Good Suffix Rule）——来跳过大量不必要的比较，从而在实践中达到亚线性时间复杂度，尤其适合长文本中的短模式匹配。

核心思想：跳着走，不回头

想象你在一本书里找一个单词。你不会一个字母一个字母地比对，而是快速扫视，发现不对就直接跳到下一个可能的位置。BM算法正是这样工作的：

• 坏字符规则：当发生不匹配时，看主串中导致不匹配的那个字符（“坏字符”），根据它在模式串中的位置决定向右滑动多少位。
• 好后缀规则：如果模式串的某一段后缀已经匹配成功，但下一个字符不匹配，则利用已匹配的“好后缀”信息，将模式串移动到下一个可能出现该后缀的位置。

实际应用中，我们通常取两个规则中能跳得更远的那个作为最终移动距离。

Python实现BM算法

下面我们用Python逐步实现BM算法。为了便于理解，我们将分别实现坏字符规则和好后缀规则，最后整合成完整的BM算法。

1. 坏字符规则的预处理

我们需要构建一个“坏字符表”，记录模式串中每个字符最右边出现的位置。

def build_bad_char_table(pattern):    """    构建坏字符表：记录每个字符在pattern中最右边出现的索引    """    bad_char = {}    for i, char in enumerate(pattern):        bad_char[char] = i  # 后面的会覆盖前面的，自然保留最右位置    return bad_char

2. 好后缀规则的预处理

好后缀规则稍微复杂一些。我们需要两个数组：suffix 和 good_suffix_shift。这里我们采用简化版实现。

def build_good_suffix_table(pattern):    """    构建好后缀表    返回一个列表，good_suffix[i] 表示当在位置i发生不匹配时，    模式串应向右移动的距离    """    m = len(pattern)    good_suffix = [0] * (m + 1)        # 第一步：计算suffix数组    suffix = [0] * (m + 1)    suffix[m - 1] = m    g = m - 1        for i in range(m - 2, -1, -1):        if i > g and suffix[i + m - 1 - (m - 1 - g)] < i - g:            suffix[i] = suffix[i + m - 1 - (m - 1 - g)]        else:            if i < g:                g = i            while g >= 0 and pattern[g] == pattern[g + m - 1 - i]:                g -= 1            suffix[i] = i - g        # 第二步：填充good_suffix数组    for i in range(m):        good_suffix[i] = m        j = 0    for i in range(m - 1, -1, -1):        if suffix[i] == i + 1:            while j < m - 1 - i:                if good_suffix[j] == m:                    good_suffix[j] = m - 1 - i                j += 1        for i in range(m - 1):        good_suffix[m - 1 - suffix[i]] = m - 1 - i        return good_suffix

3. 完整的BM算法实现

def boyer_moore_search(text, pattern):    """    使用BM算法在text中搜索pattern    返回所有匹配的起始索引列表    """    if not pattern or not text:        return []        n = len(text)    m = len(pattern)        # 预处理    bad_char = build_bad_char_table(pattern)    good_suffix = build_good_suffix_table(pattern)        matches = []    s = 0  # s是pattern相对于text的偏移量        while s <= n - m:        j = m - 1  # 从pattern末尾开始比较                # 从右向左匹配        while j >= 0 and pattern[j] == text[s + j]:            j -= 1                if j < 0:            # 完全匹配            matches.append(s)            # 移动：使用好后缀规则            s += good_suffix[0]        else:            # 不匹配            bad_char_shift = j - bad_char.get(text[s + j], -1)            good_suffix_shift = good_suffix[j]            # 取两者中较大的移动距离            s += max(bad_char_shift, good_suffix_shift)        return matches

4. 测试我们的实现

# 测试示例text = "ABAAABCDABCABC"pattern = "ABC"result = boyer_moore_search(text, pattern)print(f"匹配位置: {result}")  # 输出: 匹配位置: [4, 8, 11]

为什么选择BM算法？

相比KMP等其他字符串匹配算法，BM算法在实际应用中往往更快，尤其当模式串较长、字符集较大时。许多现代文本编辑器和Unix工具（如grep）都采用了BM或其变种（如BMS、Horspool）作为底层搜索引擎。

总结

通过本文，我们不仅理解了Boyer-Moore算法的核心思想，还用Python语言完整实现了它。虽然好后缀规则的预处理略显复杂，但掌握它能让你在面试或实际项目中脱颖而出。记住，字符串匹配不仅是算法题，更是日常开发中的实用技能。

希望这篇教程能帮助你轻松入门BM算法！如果你觉得有用，不妨动手敲一遍代码，加深理解。