這可能是全網(wǎng)最好的字符串匹配算法講解

為保證代碼嚴(yán)謹(jǐn)性，文中所有代碼均在 leetcode 刷題網(wǎng)站 AC ，大家可以放心食用。

皇上生辰之際，舉國同慶，袁記菜館作為天下第一飯店，所以被選為這次慶典的菜品供應(yīng)方，這次慶典對于袁記菜館是一項前所未有的挑戰(zhàn)，畢竟是第一次給皇上慶祝生辰，稍有不慎就是掉腦袋的大罪，整個袁記菜館內(nèi)都在緊張的布置著。此時突然有一個店小二慌慌張張跑到袁廚面前匯報，到底發(fā)生了什么事，讓店小二如此慌張呢？

袁記菜館內(nèi)

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

袁廚：發(fā)生什么事了，慢慢說，如此慌張，成何體統(tǒng)。（開店開久了，架子出來了哈）

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

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

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

找了很久，并且核對了很多遍，最后確認(rèn)皇上沒有點這道菜。菜館內(nèi)的人都松了一口氣

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

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

例：

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

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

BF算法（Brute Force）

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

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

leetcdoe 28. 實現(xiàn) strStr()

題目描述

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

示例 1:

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

示例 2:

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

題目解析

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

題目代碼

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

BM算法(Boyer-Moore)

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

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

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

壞字符規(guī)則

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

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

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

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

然后我們繼續(xù)從右往左進行比較，發(fā)現(xiàn) d 為壞字符，則需要將模式串中的 d 和壞字符對齊。

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

那么我們?yōu)槭裁匆?strong>最靠右的對應(yīng)元素與壞字符匹配呢？如果上面的例子我們沒有按照這條規(guī)則看下會產(chǎn)生什么問題。

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

我們上面一共介紹了三種移動情況，分別是下方的模式串中沒有發(fā)現(xiàn)與壞字符對應(yīng)的字符，發(fā)現(xiàn)一個對應(yīng)字符，發(fā)現(xiàn)兩個。這三種情況我們分別移動不同的位數(shù)，那我們是根據(jù)依據(jù)什么來決定移動位數(shù)的呢？下面我們給圖中的字符加上下標(biāo)。見下圖

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

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

好后綴規(guī)則

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

這里如果我們按照壞字符進行移動是不合理的，這時我們可以使用好后綴規(guī)則，那么什么是好后綴呢？

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

是不是感覺有點拗口，沒關(guān)系，我們看下圖，紅色代表壞字符，綠色代表好后綴

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

上面我們說到了，如果在模式串的頭部沒有發(fā)現(xiàn)好后綴，發(fā)現(xiàn)好后綴的子串也可以。但是為什么要強調(diào)這個頭部呢？

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

但是當(dāng)我們在頭部發(fā)現(xiàn)好后綴的子串時，是什么情況呢？

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

說到這里，壞字符和好后綴規(guī)則就算說完了，壞字符很容易理解，我們對好后綴總結(jié)一下

1.如果模式串含有好后綴，無論是中間還是頭部可以按照規(guī)則進行移動。如果好后綴在模式串中出現(xiàn)多次，則以最右側(cè)的好后綴為基準(zhǔn)。

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

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

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

之前我們剛開始說壞字符的時候，是不是有可能會出現(xiàn)負(fù)值的情況，即往左移動的情況，所以我們?yōu)榱私鉀Q這個問題，我們可以分別計算好后綴和壞字符往后滑動的位數(shù)（好后綴存在時），然后取兩個數(shù)中最大的，作為模式串往后滑動的位數(shù)。

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

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

KMP算法（Knuth-Morris-Pratt）

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

我們先來看一個實例

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

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

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

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

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

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

好啦，看完上面的圖，KMP的核心原理已經(jīng)基本搞定了，但是我們現(xiàn)在的問題是，我們應(yīng)該怎么才能知道他的最長公共前后綴的長度是多少呢？怎么知道移動多少位呢？

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

next 數(shù)組存的咱們最長公共前后綴中，前綴的結(jié)尾字符下標(biāo)。是不是感覺有點別扭，我們通過一個例子進行說明。

我們知道 next 數(shù)組之后，我們的 KMP 算法實現(xiàn)起來就很容易啦，另外我們看一下 next 數(shù)組到底是干什么用的。

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

下面我們看一下代碼，標(biāo)有詳細注釋，大家認(rèn)真看呀。

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