编辑“︁字符串匹配算法”︁（章节）

== Boyer-Moore 算法 ==
利用两个启发式规则（'''坏字符规则'''和'''好后缀规则'''）从右向左比较模式，实现更快的跳跃。

=== 坏字符规则 ===
当发现不匹配字符时，将模式向右移动，使该字符与模式中最右出现的该字符对齐。

=== 好后缀规则 ===
当发现部分匹配的后缀时，将模式向右移动，使该后缀与模式中另一个相同子串对齐。

=== 代码示例 ===
<syntaxhighlight lang="python">
def boyer_moore_search(text, pattern):
    def bad_char_heuristic(pattern):
        bad_char = [-1] * 256
        for i, c in enumerate(pattern):
            bad_char[ord(c)] = i
        return bad_char
    
    n = len(text)
    m = len(pattern)
    bad_char = bad_char_heuristic(pattern)
    positions = []
    s = 0
    
    while s <= n - m:
        j = m - 1
        while j >= 0 and pattern[j] == text[s + j]:
            j -= 1
        if j < 0:
            positions.append(s)
            s += (m - bad_char[ord(text[s + m])] if s + m < n else 1)
        else:
            s += max(1, j - bad_char[ord(text[s + j])])
    
    return positions

# 示例
text = "ABABDABACDABABCABAB"
pattern = "ABABC"
print(boyer_moore_search(text, pattern))  # 输出: [10]
</syntaxhighlight>

=== 复杂度分析 ===
* 最好情况：O(n/m)（当模式不在文本中时）
* 最坏情况：O(n×m)（当文本和模式都是重复字符时）