這一節，主要會講BM算法和KMP算法，在說之前，我們先想象一種場景，文本編輯器裡面的查找替換功能，應該都知道吧，比如，我們在word中把一個單詞替換成另一個，用的就是這個功能。你有沒有想過，這是怎麼實作的呢？
當然，用上次專欄說的BF暴力法和RK哈希比對，也可以實作這個功能，但是BM性能差，RK計算哈希比較複雜，是以實作這項功能又并不是那麼簡單的。
對于工業級的軟體開發來講，我們希望算法那可以盡可能的高效，并且可以在極端的情況下，性能也不會退化的太嚴重。
那麼，對于查找關鍵的軟體來說，是如何實作的呢？
BM算法核心思想
我們把模式串和主串的比對過程，看作模式串在主串中不停地往後滑動。當遇到不比對的字元時，BF算法 和RK算法的做法是，模式串往後滑動一位，然後從模式串的第一個字元開始重新比對。我舉個例子解釋一 下，你可以看我畫的這幅圖。
在這個例子裡，主串中的c，在模式串中是不存在的，是以，模式串向後滑動的時候，隻要c與模式串有重 合，肯定無法比對。是以，我們可以一次性把模式串往後多滑動幾位，把模式串移動到c的後面。
由現象找規律，你可以思考一下，當遇到不比對的字元時，有什麼固定的規律，可以将模式串往後多滑動幾 位呢？這樣一次性往後滑動好幾位，那比對的效率豈不是就提高了？
我們今天要講的BM算法，本質上其實就是在尋找這種規律。借助這種規律，在模式串與主串比對的過程 中，當模式串和主串某個字元不比對的時候，能夠跳過一些肯定不會比對的情況，将模式串往後多滑動幾 位。
BM算法原理分析
BM算法包含兩部分，分别是壞字元規則（bad character rule）和好字尾規則 （good suffix shift）。我們下 面依次來看，這兩個規則分别都是怎麼工作的。
- 壞字元規則
前面描述的算法，在比對的過程中，我們都是按照模式串的下标從小到大的順序，依次與主串的字元進行比對的。這種比對順序比較符合我們的思維習慣，而BM算法的比對順序比較特别，它是按照模式串下标從大到小的順序倒着比對的。
我們從模式串的末尾往前倒着比對，當我們發現某個字元沒法比對的時候。我們把這個沒有比對的字元叫作 壞字元。
然後我們拿到壞字元c在模式串查找，發現不存在c，那麼我們就可以将a後移三位，然後再從末尾字元比較，以此類推。
這時候我們發現，aca和abd還是對應不上，那麼我們就再往後移動3位讓bdc對應上我們的模式串abd嗎？不是的，因為我們發現aca末尾的a在模式串中是可以對應上的，是以再移動隻能讓abd對應上abd
當不比對的時候嗎，我們把壞字元對應的模式串中的字元下标記記做si。如果壞字元在模式串中存在，我們就把這個壞字元在模式串中的下标記做xi。如果不存在，我們就把xi記做-1。那模式串往後移動的位數就等于si-xi（注意，我們這裡說的是小表，都是字元在模式串的下标）。
但是多說一句，如果壞字元在模式串中多次出現，那我們在計算xi的時候，選擇最靠後的那個，因為這樣不會讓模式串滑動過多，導緻本來可能比對的情況被滑動略過。
利用壞字元規則，BM算法在最好的情況時，時間複雜度隻有O(n/m)。比如，主串是aaabaaabaaabaaab，模式串是baaa。每次比對都可以後移四位，這種情況就會十分高效，但是也有例外：
如果主串是aaaaaaaaaaaaa，模式串是baaaa。不但不會向後滑動，甚至會倒退，這時候，BM算法還需要用到好字尾原則。
- 好字尾原則
好字尾規則實際上跟壞字元規則的思路很類似。你看我下面這幅圖。當模式串滑動到圖中的位置的時候，模 式串和主串有2個字元是比對的，倒數第3個字元發生了不比對的情況。
這個時候該如何滑動模式串呢？當然，我們還可以利用壞字元規則來計算模式串的滑動位數，不過，我們也 可以使用好字尾處理規則。兩種規則到底如何選擇，我稍後會講。抛開這個問題，現在我們來看，好字尾規 則是怎麼工作的？
我們把已經比對的bc叫做好字尾，記做{u}。我們拿他在模式串中查找，如果找到了另一個跟{u}相比對的子串{u*}，那我們就将模式串滑動到子串{u*}與主串中{u}對齊的位置。
如果在模式串中找不到另一個等于{u}的子串，我們就直接将模式串，滑動到主串中{u}的後面，因為之前的 任何一次往後滑動，都沒有比對主串中{u}的情況。
不過這樣做，有可能就會錯過正确的比對答案
如果好字尾在模式串中不存在可比對的子串，那在我們一步一步往後滑動模式串的過程中，隻要主串中的 {u}與模式串有重合，那肯定就無法完全比對。但是當模式串滑動到字首與主串中{u}的字尾有部分重合的時 候，并且重合的部分相等的時候，就有可能會存在完全比對的情況。
是以，針對這種情況，我們不僅要看好字尾在模式串中，是否有另一個比對的子串，我們還要考察好字尾的 字尾子串，是否存在跟模式串的字首子串比對的。
所謂某個字元串s的字尾子串，就是最後一個字元跟s對齊的子串，比如abc的字尾子串就包括c, bc。所謂前 綴子串，就是起始字元跟s對齊的子串，比如abc的字首子串有a，ab。我們從好字尾的字尾子串中，找一個 最長的并且能跟模式串的字首子串比對的，假設是{v}，然後将模式串滑動到如圖所示的位置。