Boyer-Moore算法

Boyer-Moore算法是一种高效的字符串搜索算法，由Robert S. Boyer和J Strother Moore于1977年提出。该算法通过预处理模式串（待搜索的字符串）并结合两种启发式规则（坏字符规则和好后缀规则）来跳过不必要的比较，从而显著提高搜索速度。其最坏时间复杂度为 $O (n / m)$ （n为文本长度，m为模式长度），在实际应用中常接近线性时间。

算法原理[编辑 | 编辑源代码]

Boyer-Moore算法的核心思想是从模式串的末尾开始向前匹配，利用预处理信息在失配时跳过尽可能多的字符。

关键规则[编辑 | 编辑源代码]

1. 坏字符规则（Bad Character Rule）[编辑 | 编辑源代码]

当文本中的某个字符与模式串不匹配时：

若该字符在模式串中存在，则将模式串向右滑动至该字符最后一次出现的位置对齐。
若不存在，则直接跳过整个模式串。

2. 好后缀规则（Good Suffix Rule）[编辑 | 编辑源代码]

当模式串的后缀与文本匹配但前一个字符不匹配时：

找到模式串中与该后缀相同的另一子串，并将其对齐。
若不存在，则根据好后缀的后缀是否与模式串的前缀匹配来滑动。

预处理步骤[编辑 | 编辑源代码]

算法需要预先计算两个表：

坏字符表（Bad Character Table）：记录每个字符在模式串中最后一次出现的位置。
好后缀表（Good Suffix Table）：记录后缀匹配时的滑动距离。

代码实现[编辑 | 编辑源代码]

以下为Python实现的Boyer-Moore算法示例：

  
def boyer_moore(text, pattern):  
    # 预处理坏字符表  
    def build_bad_char_table(pattern):  
        table = {}  
        for i in range(len(pattern)):  
            table[pattern[i]] = i  # 记录字符最后出现的位置  
        return table  

    # 预处理好后缀表  
    def build_good_suffix_table(pattern):  
        m = len(pattern)  
        table = [0] * (m + 1)  
        border_pos = [0] * (m + 1)  

        # Case 1: 好后缀在模式串中有其他匹配  
        i = m  
        j = m + 1  
        border_pos[i] = j  
        while i > 0:  
            while j <= m and pattern[i-1] != pattern[j-1]:  
                if table[j] == 0:  
                    table[j] = j - i  
                j = border_pos[j]  
            i -= 1  
            j -= 1  
            border_pos[i] = j  

        # Case 2: 好后缀的后缀与模式串前缀匹配  
        j = border_pos[0]  
        for i in range(m + 1):  
            if table[i] == 0:  
                table[i] = j  
            if i == j:  
                j = border_pos[j]  
        return table  

    # 主算法逻辑  
    n, m = len(text), len(pattern)  
    bad_char = build_bad_char_table(pattern)  
    good_suffix = build_good_suffix_table(pattern)  
    i = 0  
    while i <= n - m:  
        j = m - 1  
        while j >= 0 and pattern[j] == text[i + j]:  
            j -= 1  
        if j == -1:  # 匹配成功  
            yield i  
            i += good_suffix[0]  
        else:  # 根据规则滑动  
            bc_shift = j - bad_char.get(text[i + j], -1)  
            gs_shift = good_suffix[j + 1]  
            i += max(bc_shift, gs_shift)  

# 示例  
text = "ABAAABCDABCABCDABCDABDE"  
pattern = "ABCDABD"  
print("匹配位置:", list(boyer_moore(text, pattern)))  # 输出: [13]

输入输出说明[编辑 | 编辑源代码]

**输入**：文本串`"ABAAABCDABCABCDABCDABDE"`和模式串`"ABCDABD"`。
**输出**：模式串在文本中的起始索引`[13]`（从0开始计数）。

实际应用案例[编辑 | 编辑源代码]

1. **文本编辑器搜索**：如VS Code、Sublime Text等工具的高性能搜索功能。 2. **病毒扫描**：快速匹配病毒特征码。 3. **生物信息学**：DNA序列模式匹配。

性能分析[编辑 | 编辑源代码]

**最佳情况**： $O (n / m)$ （如模式串完全不在文本中出现）。
**最坏情况**： $O (m n)$ （如文本和模式均为全相同字符）。
**空间复杂度**： $O (m + σ)$ （σ为字符集大小）。

与其他算法的比较[编辑 | 编辑源代码]

字符串搜索算法对比
算法	预处理时间	匹配时间	适用场景
Boyer-Moore	$O (m + σ)$	$O (n / m)$ ~ $O (m n)$	长模式串
Knuth-Morris-Pratt	$O (m)$	$O (n)$	通用
Rabin-Karp	$O (m)$	$O (n)$	多模式匹配

可视化示例[编辑 | 编辑源代码]

总结[编辑 | 编辑源代码]

Boyer-Moore算法通过逆向匹配和启发式规则大幅减少比较次数，尤其适合长模式串搜索。理解其核心规则和预处理步骤是掌握该算法的关键。