導(dǎo)語
本篇內(nèi)容研究字符串匹配問題，首先介紹字符串匹配問題诸蚕，引出Brute-Force算法及其優(yōu)化方法响疚，最后深入詳解KMP算法。文章結(jié)構(gòu)如下（全文閱讀需要30分鐘左右）：
字符串匹配問題
1字符串匹配問題是什么
"字符串A是否為字符串B的子串?如果是的話出現(xiàn)在B的哪些位置?"該問題就是字符串匹配問題蹈丸，字符串A稱為模式串，字符串B稱為主串呐芥。
2應(yīng)用
字符串匹配應(yīng)用很廣泛逻杖，比如你想在一篇文章中找到某個關(guān)鍵字所在的位置，或者是你想在一份名單中找到某個名字是否出現(xiàn)等等
Brute-Force算法
1算法核心思想
Brute-Force算法簡稱BF算法(并不是Boy Friend),算法的核心思想跟名字一樣粗暴思瘟，如下所示：
2python代碼實現(xiàn)
假設(shè)n為主串長度荸百，m為模式串長度。
每一輪字符串比較：最差的情況為模式串最后一個字與主串不同其他都相同（如模式串為AAB滨攻，主串對應(yīng)部分為AAC）够话，必須走完整個字符串才能得出結(jié)果，因此復(fù)雜度為O(m)光绕。
所有輪字符串比較：最差的情況是移動到最后一次比較才尋找得到女嘲，總共需要n-m+1次，主串通常比模式串長很多诞帐，故Brute-Force時間復(fù)雜度為O(nm)
3算法優(yōu)化思路
最壞的情況：
兩個字符串是否相同的比較很難優(yōu)化欣尼，只能逐字比較。然而比較的趟數(shù)是可以減少的停蕉，因此盡可能減少比較的趟數(shù)是算法優(yōu)化的方向愕鼓，也是KMP算法的核心思想钙态。那么，讓我們開始KMP算法的講解拒啰。
KMP算法詳解
KMP算法于1977年被提出驯绎，全稱 Knuth–Morris–Pratt 算法，包含了三位前輩名字谋旦，分別是：Donald Knuth(K), James H. Morris(M), VaughanPratt(P)
1算法核心思想
如何減少匹配的趟數(shù)呢剩失？其實在每一次匹配過程中，我們就能夠判斷后續(xù)幾次匹配是否會成功册着，算法的核心就是每次匹配過程中推斷出后續(xù)完全不可能匹配成功的匹配過程拴孤，從而減少比較的趟數(shù)，如圖所示：
因此甲捏，第一次匹配過之后演熟，就可以得出可以直接跳到第四趟再進行判斷的結(jié)論了。因為第一次匹配的時候司顿，前5個序列和主串相同芒粹，只需要對模式串進行分析，模式串出現(xiàn)了重復(fù)單元(即AB)大溜，在第一次匹配失敗后就可以直接跳躍到出現(xiàn)重復(fù)單元的位置化漆。
2next數(shù)組
next數(shù)組實質(zhì)上就是找出模式串中前后字符重復(fù)出現(xiàn)的個數(shù)，為了能夠跳躍不可能匹配的步驟钦奋。
next數(shù)組的定義為：next[i]表示模式串A[0]至A[i]這個字串座云，使得前k個字符等于后k個字符的最大值，特別的k不能取i+i,因為字串一共才i+1個字符付材，自己跟自己相等毫無意義朦拖。
最終得到next數(shù)組為：
如何確定在移動過程中需要跳過多少步呢？下圖更直觀的體現(xiàn)了跳躍的過程：
對于上述紅色部分的計算跳過長度的公式為跳過的趟數(shù)=匹配上字符串中間字符長度-重復(fù)字符串長度
跳過這些步驟后并非再從頭開始匹配厌衔，而是從重復(fù)位置開始匹配：
最終璧帝，我們不難得出如下結(jié)論：
3python代碼實現(xiàn)
1.首先建立KMP對象，初始化參數(shù)：
2.建立next數(shù)組：
第一種最簡單的構(gòu)建方案富寿，時間復(fù)雜度為O(m平法)：
第二種構(gòu)建方案睬隶，是一種遞推的方式進行構(gòu)建，時間復(fù)雜度為O(n+m):
考慮：如果next[0], next[1], ... next[x-1]均已知作喘，那么如何求出 next[x] 理疙？
我們已經(jīng)知道next[x-1],標(biāo)記next[x-1]=temp,則可以討論A[temp]和A[x]的值晕城，分2種情況討論：
第一種情況：A[temp]等于A[x]泞坦，也就是說在前一個next結(jié)果上又多了一個字符串相同的長度，因此next[x]為next[x-1]+1
第二種：當(dāng)A[temp]和A[x]不相等的時候砖顷，我們需要縮小temp,把temp變成next[temp-1]贰锁，直到A[temp]=A[x]為止赃梧。A[now]=A[x]時，就可以直接向右擴展了豌熄。
遞推構(gòu)建next數(shù)組代碼如下：
3.檢索過程代碼：
4.測試代碼：
作者原創(chuàng)授嘀，未經(jīng)授權(quán)請勿轉(zhuǎn)載
