Boyer-Moore 演算法
/ BOY-er MOOR /
大多數比對演算法由左到右掃描模式。Boyer-Moore 做了一件反直覺的事：它把模式對齊到文字後，從模式的右端往左比較。好處是右端附近的一次不匹配，就能讓你把模式一口氣向前跳許多字元，有時甚至跳過大塊文字看都不看。對長模式而言，這使它成為實務上最快的精確比對器。
兩條規則決定不匹配後跳多遠，你取兩者中較大的。壞字元規則：看造成不匹配的那個文字字元。若該字元根本不在模式中出現，你可以把模式整個滑過它；若它有出現，就滑動使模式中該字元最右的那份對齊到它底下。好後綴規則：若你在失敗前已匹配了模式的某個後綴，就移動使該已匹配後綴的另一處出現（或模式中與其尾端相符的某前綴）對齊，這很像 KMP 的失敗構想，但作用在後綴上。兩條規則都在 O(m + 字母表大小) 時間內從模式預先算好。有了它們，在一般文字上 Boyer-Moore 檢查的字元遠少於 n——它可以在次線性時間執行，理想情況下約 O(n/m) 次比較。
Boyer-Moore 發表於 1977 年，是你作業系統的 grep 和許多編輯器實際採用的方法，常以只用壞字元的簡化形式（即 Boyer-Moore-Horspool）出現。誠實的提醒：它著稱的速度是平均情況、大字母表、長模式的現象；純壞字元版本仍有 O(n*m) 的最壞情況（加上好後綴規則的完整 Boyer-Moore，以及 Galil 變體，才恢復線性的最壞情況界限）。在像 DNA 這種小字母表上，跳躍變短，相對 KMP 的優勢縮小。它深層的功課是：由右往左掃描，讓來自模式末端的資訊驅動大而安全的跳躍——這和 KMP「永不重讀」的紀律是不同的檔位。
P = "NEEDLE" 對上 T = "...XXXXXXNEEDLE..."。對齊 P，從右邊比較：P 的 'E' 對上它底下的文字字元，設為 'X'。'X' 不在 "NEEDLE" 中，所以壞字元規則把整個模式滑過那個 'X'——一次六格，跳過從未檢查的字元。對照 KMP，它會把那些文字字元每一個都讀過。
由右往左掃描，一個不在模式中的文字字元讓 Boyer-Moore 越過它跳開、完全不碰。
那個「實務上次線性」的速度需要相當大的字母表和稍長的模式；在小字母表上或只用壞字元規則時，最壞情況仍是 O(n*m)。當你需要保證的線性界限時，請加上好後綴規則（或 Galil 規則）。