字符串匹配算法

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

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

袁記菜館內(nèi)

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

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

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

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

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

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

通過上面的一個(gè)例子，讓我們簡(jiǎn)單了解了字符串匹配，下面我們一起來詳細(xì)了解一下吧。

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

例：

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

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

BF算法（Brute Force）

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

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

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

題目描述

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

示例 1:

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

示例 2:

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

題目解析

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

題目代碼

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

BM算法(Boyer-Moore)

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

如上圖所示，如果我們利用 BF 算法，遇到不匹配字符時(shí)，每次右移一位模式串，再重新從頭進(jìn)行匹配，我們觀察一下，我們的模式串 abcdex 中每個(gè)字符都不一樣，但是我們第一次進(jìn)行字符串匹配時(shí)，abcde 都匹配成功，到 x 時(shí)失敗，又因?yàn)槟Ｊ酱课欢疾幌嗤晕覀儾恍枰倜看斡乙埔晃?，再重新比較，我們可以直接跳過某些步驟。如下圖

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

壞字符規(guī)則

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

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

那我們?cè)谀Ｊ酱姓业綁淖址撛趺崔k呢？見下圖

此時(shí)我們的壞字符為 f , 我們?cè)谀Ｊ酱校檎野l(fā)現(xiàn)含有壞字符 f ,我們則需要移動(dòng)模式串 T ,將模式串中的 f 和壞字符對(duì)齊。見下圖。

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

那么我們?cè)趤硭伎家幌逻@種情況，那就是模式串中含有多個(gè)壞字符怎么辦呢？

那么我們?yōu)槭裁匆屪羁坑业膶?duì)應(yīng)元素與壞字符匹配呢？如果上面的例子我們沒有按照這條規(guī)則看下會(huì)產(chǎn)生什么問題。

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

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

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

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

好后綴規(guī)則

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

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

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

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

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

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

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

但是當(dāng)我們?cè)陬^部發(fā)現(xiàn)好后綴的子串時(shí)，是什么情況呢？

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

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

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

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

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

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

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

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

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

KMP算法（Knuth-Morris-Pratt）

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

我們先來看一個(gè)實(shí)例

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

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

在上面的例子中我們提到了一個(gè)名詞，最長(zhǎng)公共前后綴，這個(gè)是什么意思呢？下面我們通過一個(gè)較簡(jiǎn)單的例子進(jìn)行描述。

此時(shí)我們?cè)诩t色陰影處匹配失敗，綠色為匹配成功部分，則我們觀察匹配成功的部分。

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

我們的最長(zhǎng)公共前后綴如下圖，則我們需要這樣移動(dòng)

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

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

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

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

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

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

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

責(zé)任編輯：xj

原文標(biāo)題：字符串匹配算法詳解

文章出處：【微信公眾號(hào)：算法與數(shù)據(jù)結(jié)構(gòu)】歡迎添加關(guān)注！文章轉(zhuǎn)載請(qǐng)注明出處。