字符串匹配算法詳解

爲保證代碼嚴謹性，文中所有代碼均在 leetcode 刷題網站 AC ，大家可以放心食用。

皇上生辰之際，舉國同慶，袁記菜館作爲天下第一飯店，所以被選爲這次慶典的菜品供應方，這次慶典對於袁記菜館是一項前所未有的挑戰，畢竟是第一次給皇上慶祝生辰，稍有不慎就是掉腦袋的大罪，整個袁記菜館內都在緊張的佈置着。此時突然有一個店小二慌慌張張跑到袁廚面前彙報，到底發生了什麼事，讓店小二如此慌張呢？

袁記菜館內

店小二：不好了不好了，掌櫃的，出大事了。

袁廚：發生什麼事了，慢慢說，如此慌張，成何體統。（開店開久了，架子出來了哈）

店小二：皇上按照咱們菜單點了 666 道菜，但是咱們做西湖醋魚的師傅請假回家結婚了，不知道皇上有沒有點這道菜，如果點了這道菜，咱們做不出來，那咱們店可就完了啊。

（袁廚聽了之後，嚇得一屁股坐地上了，緩了半天說道）

袁廚：別說那麼多了，快給我找找皇上點的菜裏面，有沒有這道菜！

找了很久，並且覈對了很多遍，最後確認皇上沒有點這道菜。菜館內的人都鬆了一口氣

通過上面的一個例子，讓我們簡單瞭解了字符串匹配，下面我們一起來詳細瞭解一下吧。

**字符串匹配：**設 S 和 T 是給定的兩個串，在主串 S 中找到模式串 T 的過程稱爲字符串匹配，如果在主串 S 中找到模式串 T ，則稱匹配成功，函數返回 T 在 S 中首次出現的位置，否則匹配不成功，返回  -1。

例：

在上圖中，我們試圖找到模式串 T = baab, 在**主串 S = abcabaabcabac **中第一次出現的位置，即爲紅色陰影部分， T 第一次在 S 中出現的位置下標爲 4 （ 字符串的首位下標是 0 ），所以返回 4。如果模式串 T 沒有在主串 S 中出現，則返回 -1。

解決上面問題的算法我們稱之爲字符串匹配算法，今天我們來介紹三種字符串匹配算法，大家記得打卡呀，說不準面試的時候就問到啦。

BF 算法（Brute Force）

這個算法很容易理解，就是我們將模式串和主串進行比較，一致時則繼續比較下一字符，直到比較完整個模式串。不一致時則將模式串後移一位，重新從模式串的首位開始對比，重複剛纔的步驟下面我們看下這個方法的動圖解析，看完肯定一下就能搞懂啦。

通過上面的代碼是不是一下就將這個算法搞懂啦，下面我們用這個算法來解決下面這個經典題目吧。

leetcdoe 28. 實現 strStr()

題目描述

給定一個 haystack 字符串和一個 needle 字符串，在 haystack 字符串中找出 needle 字符串出現的第一個位置 (從 0 開始)。如果不存在，則返回  -1。

示例 1:

輸入: haystack = "hello", needle = "ll" 輸出: 2

示例 2:

輸入: haystack = "aaaaa", needle = "bba" 輸出: -1

題目解析

其實這個題目很容易理解，但是我們需要注意的是一下幾點，比如我們的模式串爲 0 時，應該返回什麼，我們的模式串長度大於主串長度時，應該返回什麼，也是我們需要注意的地方。下面我們來看一下題目代碼吧。

題目代碼

我們看一下 BF 算法的另一種算法（顯示回退），其實原理一樣，就是對代碼進行了一下修改，只要看完咱們的動圖，這個也能夠一下就能看懂，大家可以結合下面代碼中的註釋和動圖進行理解。

BM 算法 (Boyer-Moore)

我們剛纔說過了 BF 算法，但是 BF 算法是有缺陷的，比如我們下面這種情況

如上圖所示，如果我們利用 BF 算法，遇到不匹配字符時，每次右移一位模式串，再重新從頭進行匹配，我們觀察一下，我們的模式串 abcdex 中每個字符都不一樣，但是我們第一次進行字符串匹配時，abcde 都匹配成功，到 x 時失敗，又因爲模式串每位都不相同，所以我們不需要再每次右移一位，再重新比較，我們可以直接跳過某些步驟。如下圖

我們可以跳過其中某些步驟，直接到下面這個步驟。那我們是依據什麼原則呢？

壞字符規則

我們之前的 BF 算法是從前往後進行比較 ，BM 算法是從後往前進行比較，我們來看一下具體過程，我們還是利用上面的例子。

BM 算法是從後往前進行比較，此時我們發現比較的第一個字符就不匹配，我們將主串這個字符稱之爲壞字符，也就是 f , 我們發現壞字符之後，模式串 T 中查找是否含有該字符 f，我們發現並不存在 f，此時我們只需將模式串右移到壞字符的後面一位即可。如下圖

那我們在模式串中找到壞字符該怎麼辦呢？見下圖

此時我們的壞字符爲 f , 我們在模式串中，查找發現含有壞字符  f , 我們則需要移動模式串 T , 將模式串中的 f 和壞字符對齊。見下圖。

然後我們繼續從右往左進行比較，發現 d 爲壞字符，則需要將模式串中的 d 和壞字符對齊。

那麼我們在來思考一下這種情況，那就是模式串中含有多個壞字符怎麼辦呢？

那麼我們爲什麼要讓最靠右的對應元素與壞字符匹配呢？如果上面的例子我們沒有按照這條規則看下會產生什麼問題。

如果沒有按照我們上述規則，則會漏掉我們的真正匹配。我們的主串中是含有 babac 的，但是卻沒有匹配成功，所以應該遵守最靠右的對應字符與壞字符相對的規則。

我們上面一共介紹了三種移動情況，分別是下方的模式串中沒有發現與壞字符對應的字符，發現一個對應字符，發現兩個。這三種情況我們分別移動不同的位數，那我們是根據依據什麼來決定移動位數的呢？下面我們給圖中的字符加上下標。見下圖

下面我們來考慮一下這種情況。

此時這種情況肯定是不行的，不往右移動，甚至還有可能左移，那麼我們有沒有什麼辦法解決這個問題呢？繼續往下看吧。

好後綴規則

好後綴其實也很容易理解，我們之前說過 BM 算法是從右往左進行比較，下面我們來看下面這個例子。

這裏如果我們按照壞字符進行移動是不合理的，這時我們可以使用好後綴規則，那麼什麼是好後綴呢？

BM 算法是從右往左進行比較，發現壞字符的時候此時 cac  已經匹配成功，在紅色陰影處發現壞字符。此時已經匹配成功的  cac 則爲我們的好後綴，此時我們拿它在模式串中查找，如果找到了另一個和好後綴相匹配的串，那我們就將另一個和好後綴相匹配的串 ，滑到和好後綴對齊的位置。

是不是感覺有點拗口，沒關係，我們看下圖，紅色代表壞字符，綠色代表好後綴

上面那種情況搞懂了，但是我們思考一下下面這種情況

上面我們說到了，如果在模式串的頭部沒有發現好後綴，發現好後綴的子串也可以。但是爲什麼要強調這個頭部呢？

我們下面來看一下這種情況

但是當我們在頭部發現好後綴的子串時，是什麼情況呢？

下面我們通過動圖來看一下某一例子的具體的執行過程

說到這裏，壞字符和好後綴規則就算說完了，壞字符很容易理解，我們對好後綴總結一下

1. 如果模式串含有好後綴，無論是中間還是頭部可以按照規則進行移動。如果好後綴在模式串中出現多次，則以最右側的好後綴爲基準。

2. 如果模式串頭部含有好後綴子串則可以按照規則進行移動，中間部分含有好後綴子串則不可以。

3. 如果在模式串尾部就出現不匹配的情況，即不存在好後綴時，則根據壞字符進行移動，這裏有挺多文章沒有提到，是個需要特別注意的地方，我是在這個論文裏找到答案的，感興趣的同學可以看下。

Boyer R S，Moore J S. A fast string searching algorithm［J］. Communications of the ACM，1977，10：762-772.

之前我們剛開始說壞字符的時候，是不是有可能會出現負值的情況，即往左移動的情況，所以我們爲了解決這個問題，我們可以分別計算好後綴和壞字符往後滑動的位數（好後綴存在時），然後取兩個數中最大的，作爲模式串往後滑動的位數。

這破圖畫起來是真費勁啊。下面我們來看一下算法代碼，代碼有點長，我都標上了註釋也在網站上 AC 了，如果各位感興趣可以看一下，不感興趣的話，理解壞字符和好後綴規則即可。可以直接跳到 KMP 部分

我們來理解一下我們代碼中用到的兩個數組，因爲兩個規則的移動位數，只與模式串有關，與主串無關，所以我們可以提前求出每種情況的移動情況，保存到數組中。

KMP 算法（Knuth-Morris-Pratt）

我們剛纔講了 BM 算法，雖然不是特別容易理解，但是如果你用心看的話肯定可以看懂的，我們再來看一個新的算法，這個算法是考研時必考的算法。實際上 BM 和 KMP 算法的本質是一樣的，你理解了 BM 再來理解 KMP 那就是分分鐘的事啦。

我們先來看一個實例

注：爲了讓讀者更容易理解，我們將指針移動改成了模式串移動，兩者相對與主串的移動是一致的，重新比較時都是從指針位置繼續比較。

通過上面的實例是不是很快就能理解 KMP 算法的思想了，我們繼續往下看。

在上面的例子中我們提到了一個名詞，最長公共前後綴，這個是什麼意思呢？下面我們通過一個較簡單的例子進行描述。

此時我們在紅色陰影處匹配失敗，綠色爲匹配成功部分，則我們觀察匹配成功的部分。

我們來看一下匹配成功部分的所有前後綴

我們的最長公共前後綴如下圖，則我們需要這樣移動

好啦，看完上面的圖，KMP 的核心原理已經基本搞定了，但是我們現在的問題是，我們應該怎麼才能知道他的最長公共前後綴的長度是多少呢？怎麼知道移動多少位呢？

剛纔我們在 BM 中說到，我們移動位數跟主串無關，只跟模式串有關，跟我們的 bc,suffix,prefix 數組的值有關，我們通過這些數組就可以知道我們每次移動多少位啦，其實 KMP 也有一個數組，這個數組叫做 next 數組，那麼這個 next 數組****存的是什麼呢？

next 數組存的咱們最長公共前後綴中，前綴的結尾字符下標。是不是感覺有點彆扭，我們通過一個例子進行說明。

我們知道 next 數組之後，我們的 KMP 算法實現起來就很容易啦，另外我們看一下 next 數組到底是幹什麼用的。

剩下的就不用說啦，完全一致啦，咱們將上面這個例子，翻譯成和咱們開頭對應的動畫大家看一下。

下面我們看一下代碼，標有詳細註釋，大家認真看呀。

注：很多教科書的 next 數組表示方式不一致，理解即可

好啦好啦先就寫這麼多吧，累屁了，剩下的幾種就先不寫了，覺得這個文章對你有幫助的話，歡迎各位點贊，評論，在看，轉發。哦，我還沒評論功能。哈哈

我是袁廚，一個酷愛用動圖解算法的年輕人，一個酷愛做飯的程序員，一個想和你一起進步的小老弟。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/AmP1LU-rGJNXlSruVH2sng