Boyer-Moore：向后看的先知

算法背后的故事：排除的效率

想象你正在一长串句子中寻找 apple 这个单词。 标准做法是先看第一个字母：a。 但在 1977 年，Robert S. Boyer 和 J Strother Moore 提出了一个激进的想法：如果我们先看最后一个字母呢？

如果文本中的第 5 个字母是 x，而你要找的是 apple，你瞬间就能明白两件事：

1. x 不是 e。（匹配失败）
2. x 甚至根本不在 apple 这个单词里。

基于第 2 点，你不需要向后移动 1 个字符，你可以瞬间向后跳 5 個字符。你甚至连看都没看，就直接跳过了 4 个字母。

这就是 排除启发式 (Heuristic of Exclusion)。它是 Boyer-Moore 算法在实践中通常成为最快字符串搜索算法的原因。它是大多数文本编辑器和浏览器中“查找”(Ctrl+F) 命令背后的核心大脑。

为什么需要它？

Boyer-Moore 是 亚线性搜索 (Sub-linear Search) 的王者。 在很多情况下，它甚至不需要阅读文本中的每一个字符就能找到目标。

• 文本编辑器： 当你在 50MB 的文件中搜索时，Boyer-Moore 让搜索感觉是瞬间完成的。
• Grep： 著名的 Unix 工具使用了这种逻辑的简化版本。
• 大规模字符集： 在处理英文文本时效果极佳，因为“不匹配”触发巨大跳跃的概率非常高。

算法是如何“思考”的

这个算法是一个大胆的战略家，它使用两条规则来决定跳多远：

1. 坏字符规则 (Bad Character Rule)： 如果文本中的字符与模式串中的不匹配，Boyer-Moore 会查看模式串：“我还有其他地方包含这个字符吗？”

   • 如果没有：直接跳过整个模式串的长度。
   • 如果有：将模式串对齐，使该字符匹配，然后再次尝试。

2. 好后缀规则 (Good Suffix Rule)： 如果你已经匹配到了单词的末尾（“后缀”），但就在它前面失败了，算法会问：“这个后缀在我单词的其他地方出现过吗？”它利用这个信息跳到下一个潜在的对齐位置。

通过结合这两条规则，Boyer-Moore 将大部分时间花在 “不去阅读” 文本上。

工程决策：现实世界的冠军

虽然 KMP 在理论上非常优雅，但在 现实世界的文本 中，Boyer-Moore 通常更快。

• 复杂度： 它的最坏情况是 $O(N \cdot M)$，但它的平均情况是 $O(N / M)$。是的，你没看错：你的模式串越长，搜索速度反而越快（因为跳跃步长变大了）。
• 实现： 它比 KMP 更难实现，这就是为什么许多工程师会使用它的简化版本，即 Boyer-Moore-Horspool。

实现参考 (Python - 简化的 Horspool 版本)

def horspool_search(text, pattern):
    n, m = len(text), len(pattern)
    if m > n: return -1
    
    # 1. 预计算坏字符表
    # “如果我看到这个字符，我能跳多远？”
    skip = {char: m for char in set(text)}
    for i in range(m - 1):
        skip[pattern[i]] = m - i - 1
        
    k = m - 1 # 在文本中的位置
    while k < n:
        j = m - 1 # 在模式串中的位置 (从右向左讀！)
        i = k
        
        while j >= 0 and text[i] == pattern[j]:
            i -= 1
            j -= 1
            
        if j == -1:
            return i + 1 # 找到匹配！
            
        # 2. 信心的一跃 (The Leap of Faith)
        k += skip.get(text[k], m)
        
    return -1

# 使用示例
# text = "TRUST_HARD_WORK_AND_LUCK"
# pattern = "WORK"
# print(horspool_search(text, pattern)) # 输出: 11

小结

Boyer-Moore 教会我们：知道该忽略什么 是智慧的高级形式。通过从末尾开始并寻找跳过的理由，它证明了我们不需要看清每一个细节也能理解整体。在数据世界中，通往答案最快的路往往是那些跳过问题最多的路。