编辑“︁Boyer-Moore算法”︁

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

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

=== 关键规则 ===  
==== 1. 坏字符规则（Bad Character Rule） ====  
当文本中的某个字符与模式串不匹配时：  
* 若该字符在模式串中存在，则将模式串向右滑动至该字符最后一次出现的位置对齐。  
* 若不存在，则直接跳过整个模式串。  

==== 2. 好后缀规则（Good Suffix Rule） ====  
当模式串的后缀与文本匹配但前一个字符不匹配时：  
* 找到模式串中与该后缀相同的另一子串，并将其对齐。  
* 若不存在，则根据好后缀的后缀是否与模式串的前缀匹配来滑动。  

=== 预处理步骤 ===  
算法需要预先计算两个表：  
* '''坏字符表（Bad Character Table）'''：记录每个字符在模式串中最后一次出现的位置。  
* '''好后缀表（Good Suffix Table）'''：记录后缀匹配时的滑动距离。  

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

<syntaxhighlight lang="python">  
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]  
</syntaxhighlight>  

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

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

== 性能分析 ==  
* **最佳情况**：<math>O(n/m)</math>（如模式串完全不在文本中出现）。  
* **最坏情况**：<math>O(mn)</math>（如文本和模式均为全相同字符）。  
* **空间复杂度**：<math>O(m + \sigma)</math>（σ为字符集大小）。  

== 与其他算法的比较 ==  
{| class="wikitable"  
|+ 字符串搜索算法对比  
! 算法 !! 预处理时间 !! 匹配时间 !! 适用场景  
|-  
| Boyer-Moore || <math>O(m + \sigma)</math> || <math>O(n/m)</math> ~ <math>O(mn)</math> || 长模式串  
|-  
| Knuth-Morris-Pratt || <math>O(m)</math> || <math>O(n)</math> || 通用  
|-  
| Rabin-Karp || <math>O(m)</math> || <math>O(n)</math> || 多模式匹配  
|}  

== 可视化示例 ==  
<mermaid>  
graph LR  
    A[文本: ABAAABCDABC...] --> B[模式: ABCDABD]  
    B -->|从右向左匹配| C{匹配？}  
    C -->|否| D[坏字符规则滑动]  
    C -->|是| E[好后缀规则滑动]  
</mermaid>  

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

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:搜索算法]]