KMP 的匹配是從模式串的開頭開始匹配的，而 1977 年，德克薩斯大學(xué)的 Robert S. Boyer 教授和 J Strother Moore 教授發(fā)明了一種新的字符串匹配算法：Boyer-Moore 算法，簡稱 BM 算法。該算法從模式串的尾部開始匹配，且擁有在最壞情況下 O(N) 的時間復(fù)雜度。在實踐中，比 KMP 算法的實際效能高。

BM 算法定義了兩個規(guī)則：

• 壞字符規(guī)則：當(dāng)文本串中的某個字符跟模式串的某個字符不匹配時，我們稱文本串中的這個失配字符為壞字符，此時模式串需要向右移動，移動的位數(shù) = 壞字符在模式串中的位置 - 壞字符在模式串中最右出現(xiàn)的位置。此外，如果"壞字符"不包含在模式串之中，則最右出現(xiàn)位置為 -1。
• 好后綴規(guī)則：當(dāng)字符失配時，后移位數(shù) = 好后綴在模式串中的位置 - 好后綴在模式串上一次出現(xiàn)的位置，且如果好后綴在模式串中沒有再次出現(xiàn)，則為 -1。

下面舉例說明 BM 算法。例如，給定文本串“HERE IS A SIMPLE EXAMPLE”，和模式串“EXAMPLE”，現(xiàn)要查找模式串是否在文本串中，如果存在，返回模式串在文本串中的位置。

1.首先，"文本串"與"模式串"頭部對齊，從尾部開始比較。"S"與"E"不匹配。這時，"S"就被稱為"壞字符"（bad character），即不匹配的字符，它對應(yīng)著模式串的第 6 位。且"S"不包含在模式串"EXAMPLE"之中（相當(dāng)于最右出現(xiàn)位置是 -1），這意味著可以把模式串后移 6-(-1)=7 位，從而直接移到"S"的后一位。

http://wiki.jikexueyuan.com/project/kmp-algorithm/images/41.png" alt="" />

2.依然從尾部開始比較，發(fā)現(xiàn)"P"與"E"不匹配，所以"P"是"壞字符"。但是，"P"包含在模式串"EXAMPLE"之中。因為“P”這個“壞字符”對應(yīng)著模式串的第 6 位（從 0 開始編號），且在模式串中的最右出現(xiàn)位置為 4，所以，將模式串后移 6-4=2 位，兩個"P"對齊。

http://wiki.jikexueyuan.com/project/kmp-algorithm/images/42.png" alt="" />

http://wiki.jikexueyuan.com/project/kmp-algorithm/images/43.png" alt="" />

3.依次比較，得到 “MPLE”匹配，稱為"好后綴"（good suffix），即所有尾部匹配的字符串。注意，"MPLE"、"PLE"、"LE"、"E"都是好后綴。

http://wiki.jikexueyuan.com/project/kmp-algorithm/images/44.png" alt="" />

4.發(fā)現(xiàn)“I”與“A”不匹配：“I”是壞字符。如果是根據(jù)壞字符規(guī)則，此時模式串應(yīng)該后移 2-(-1)=3 位。問題是，有沒有更優(yōu)的移法？

http://wiki.jikexueyuan.com/project/kmp-algorithm/images/45.png" alt="" />

http://wiki.jikexueyuan.com/project/kmp-algorithm/images/46.png" alt="" />

5.更優(yōu)的移法是利用好后綴規(guī)則：當(dāng)字符失配時，后移位數(shù) = 好后綴在模式串中的位置 - 好后綴在模式串中上一次出現(xiàn)的位置，且如果好后綴在模式串中沒有再次出現(xiàn)，則為 -1。

所有的“好后綴”（MPLE、PLE、LE、E）之中，只有“E”在“EXAMPLE”的頭部出現(xiàn)，所以后移 6-0=6 位。

可以看出，“壞字符規(guī)則”只能移3位，“好后綴規(guī)則”可以移 6 位。每次后移這兩個規(guī)則之中的較大值。這兩個規(guī)則的移動位數(shù)，只與模式串有關(guān)，與原文本串無關(guān)。

http://wiki.jikexueyuan.com/project/kmp-algorithm/images/47.png" alt="" />

6.繼續(xù)從尾部開始比較，“P”與“E”不匹配，因此“P”是“壞字符”，根據(jù)“壞字符規(guī)則”，后移 6 - 4 = 2 位。因為是最后一位就失配，尚未獲得好后綴。

http://wiki.jikexueyuan.com/project/kmp-algorithm/images/48.png" alt="" />

由上可知，BM 算法不僅效率高，而且構(gòu)思巧妙，容易理解。