4. 擴(kuò)展 1：BM 算法

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

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

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

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

1.首先，"文本串"與"模式串"頭部對(duì)齊，從尾部開(kāi)始比較。"S"與"E"不匹配。這時(shí)，"S"就被稱為"壞字符"（bad character），即不匹配的字符，它對(duì)應(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.依然從尾部開(kāi)始比較，發(fā)現(xiàn)"P"與"E"不匹配，所以"P"是"壞字符"。但是，"P"包含在模式串"EXAMPLE"之中。因?yàn)椤癙”這個(gè)“壞字符”對(duì)應(yīng)著模式串的第 6 位（從 0 開(kāi)始編號(hào)），且在模式串中的最右出現(xiàn)位置為 4，所以，將模式串后移 6-4=2 位，兩個(gè)"P"對(duì)齊。

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ī)則，此時(shí)模式串應(yīng)該后移 2-(-1)=3 位。問(wèn)題是，有沒(méi)有更優(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í)，后移位數(shù) = 好后綴在模式串中的位置 - 好后綴在模式串中上一次出現(xiàn)的位置，且如果好后綴在模式串中沒(méi)有再次出現(xiàn)，則為 -1。

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

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

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

6.繼續(xù)從尾部開(kāi)始比較，“P”與“E”不匹配，因此“P”是“壞字符”，根據(jù)“壞字符規(guī)則”，后移 6 - 4 = 2 位。因?yàn)槭亲詈笠晃痪褪洌形传@得好后綴。

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

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