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 教會我們：知道該忽略什麼 是智慧的高級形式。透過從末尾開始並尋找跳過的理由，它證明了我們不需要看清每一個細節也能理解整體。在數據世界中，通往答案最快的路往往是那些跳過問題最多的路。