字串匹配Boyer-Moore演算法：文字編輯器中的查詢功能是如何實現的？

關於字串匹配演算法有很多，之前我有講過一篇 KMP 匹配演算法： 圖解字串匹配 KMP 演算法 ，不懂 kmp 的建議看下，寫的還不錯，這個演算法雖然很牛逼，但在實際中用的並不是特別多。至於選擇哪一種字串匹配演算法，在不同的場景有不同的選擇。

在我們平時文件裡的字元查詢裡

採用的就是 Boyer-Moore 匹配演算法了，簡稱 BM 演算法。這個演算法也是有一定的難度，不過今天，我選用一個例子，帶大家讀懂這個 字串匹配 BM 演算法

，看完這篇文章，保證你能夠掌握這個演算法的思想。

首先我先給出一個字串和一個模式串

接下來我們要在字串中查詢有沒有和模式串匹配的字串，步驟如下：

壞字元

1、

和其他的匹配演算法不同，BM 匹配演算法，是從模式串的 尾部 開始匹配的，所以我們把字串和模式串的 尾部

對齊。

顯然，從圖中我們可以發現，s 和 e 並不匹配。這時我們把“s” 稱之為 壞字元 ，即代表不匹配的字元。而且我們可以發現，s 和模式串中的任意一個字元都不匹配，所以這時，我們可以直接把模式串移動到 s 的後面。

2、

從圖中可以看出，此時 p 和 e 不匹配，所以 p 是一個 壞字元 ，不過，我們可以發現 “p” 包含在模式串中

所以，我們不能像第一步那樣，把模式串直接全部移到 p 的後面去，而是移動兩位，讓兩個 p 對齊。

4、

那麼問題來了， 當我們碰到碰到壞字元的時候，該移動幾位呢？

下面我和大家講一下這個問題，首先我們要算出 模式串 中兩個字元的下標。這兩個字元分別是

（1）模式串中與壞字元對應的那個字元的下標，在我們上面那個例子中，就是 e。

顯然，這個 e 的下標是 6（從0開始算起）。我們用變數 t1 來代表這個字元的下標吧。

（2）壞字元在模式串中的下標，在我們上面那個例子中，壞字元在模式串中的下標為 4，我們用變數 t2 來代表這個下標，如圖

找出這兩個字元的下標之後，我們就可以計算移動的位數了

移動的位數 = t1 - t2。

例如上面的例子步驟 2 中 t1 = 6, t2 = 4,所以移動了 t1 - t2 = 2 位。

（1）這個時候可能有人會問了，那如果模式串中有多個 p 呢？

答是如果有多個，我們只計算最右邊的那個（當然是移動的位數越少越安全了）

（2）可能又有人會問，那如果模式串中並不存在壞字元呢？例如步驟1

答是如果不存在的話，我們把 t2 賦值為 -1，即 t2 = -1。所以我們步驟 1 中移動了 t1 - t2 = 6 - (-1) = 7 位。

好了，現在我們已經解決了 遇到壞字元之後，應該移動多少位的問題 了。

好字尾

我們繼續匹配

5、

匹配，所以繼續匹配前面的字元

6、

匹配，繼續匹配前面的字元

7、

匹配，繼續匹配前面的字元

8、

匹配，繼續匹配前面的字元

9、

遇到壞字元 i，按照我們前面的規則，可以計算出 t1 = 2(就是a的下標)。t2 = -1(因為模式串不存在壞字元)。所以移動的位數是 t1 - t2 = 3。

但是，我想問一下，這是最好的移動方式嗎？有沒有更好的移動方法呢？接下來我就和大家介紹一種更好的方法，這種方法就是根據 好字尾 來移動位數。首先我們先介紹下啥的 好字尾 。

在上面的例子中，我們發現 "mple" 是能夠成功匹配的

我們把這些能夠成功匹配的子串，稱之為 好字尾

，所以呢，e，le，elp，mple 都是好字尾

因為 e, le, elp在之前的步驟中，也是能夠成功匹配。不過 mple 是最長的好字尾。

接下來我們要 在模式串的前面尋找與好字尾匹配的子串 ，這句話的意思就是說，我們要在模式串中尋找這樣一個子串s：s 與好字尾匹配，並且s中的字元不能與好字尾有重疊。

我舉個例子吧，例如有模式串 abcddab，然後好字尾分別是 b, ab, dab。那麼與好字尾匹配的字串有 b,ab。（因為abcddab前面中的b可以與好字尾 b 匹配，前面的 bc 與好字尾 bc 匹配）。不過,沒有與好字尾 dab 匹配的子串。

那麼問題來了，如果我們找到了多個這樣的子串的話，我們要選擇哪一個呢？例如上面我們找到了兩個，分別是 a，ab。

這個時候，我們選擇與比較長的那個好字尾匹配的子串，例如，上面的例子中，我們會選擇 ab，我們把這個被選中的子串（ab）稱之為 好字首 吧（我是為了後面方便描述，才給它這個一個稱呼）。

找出了 好字尾 和 好字首 之後 ，我們就可以知道要移動幾位了，公式如下：

移動的位數 = 好字尾的下標 - 好字首的下標。

當然，好字尾有多個，我們是選擇和好字首匹配的那一個。那麼 好字尾的下標怎麼算呢？ ，計算方法是按照好字尾的 最後一個字元的下標為準 ，例如模式串 abcddab 中好字尾 ab 的下標為 6（下標從 0 開始算起）。好字首下標的方法也是一樣，以最後一個字元的下標位準，例如模式串 abcddab 中，好字首 ab 的下標為 1。

這裡可能有人會問，那如果不存在這樣的好字首呢？如果不存在的話，就用 -1 充當好字首的下標。

知道了移動位數之後，我們繼續來匹配我們上面的例子

10、

好字尾是 e, le, ple, mple，但是模式串中只有一個子串能夠與好字尾 e 匹配，所以好字首為 e。

顯然，這個時候好字首 e 的下標為 0,好字尾 e 的下標為 6，所以移動的位數為 6。如果按照我們最開始壞字元的移動規則的話，只能移動 3 位，而用好字尾可以移動 6 位。

選擇壞字元的規則還是好字尾？

11、

可能有人會問，兩個規則我們應該要選擇哪一個呢？

答案很簡單，把兩個規則的移動位數都算出來，選擇移動位數多的就是了。

這裡 p 是壞字元，並且不存在好字尾，所以採用壞字元的規則，移動 2 位。

12、

這個時候，我們可以發現，模式串的字元全部都匹配了，這也意味著匹配結束了。

總結

這篇文章我是採用直接舉例子的方式來講，我覺得這樣反而容易懂，並且在講的過程中，可能沒有講的那麼全，這是因為我不想說的太全，因為把所有情況都羅列處理的話，相信你容易暈。所以我才用這種方式，讓你先懂了這個 BM 的演算法思想，之後的細節，你可以再去琢磨。

為了講清楚這個演算法，也算是絞盡腦汁，特別是為了能夠以最簡單的方式來講解 好字尾 的規則，停筆思索了好久，最後也百度搜索了幾篇文章，看看別人都怎麼講，還翻開了我之前購買的資料結構與演算法的專欄，，，最後結合自己的想法寫了出來。希望這篇文章，能夠讓你讀懂給 BM 演算法，這個演算法的核心就是壞字元和好字尾了，相信你一定能夠搞懂！後面會連續講解幾篇與 樹 有關的文章。