導(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代碼實(shí)現(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), Vaughan Pratt(P)01算法核心思想

如何減少匹配的趟數(shù)呢？其實(shí)在每一次匹配過程中，我們就能夠判斷后續(xù)幾次匹配是否會成功，算法的核心就是每次匹配過程中推斷出后續(xù)完全不可能匹配成功的匹配過程，從而減少比較的趟數(shù)，如圖所示：

因此，第一次匹配過之后，就可以得出可以直接跳到第四趟再進(jìn)行判斷的結(jié)論了。因?yàn)榈谝淮纹ヅ涞臅r候，前5個序列和主串相同，只需要對模式串進(jìn)行分析，模式串出現(xiàn)了重復(fù)單元(即AB)，在第一次匹配失敗后就可以直接跳躍到出現(xiàn)重復(fù)單元的位置。

2next數(shù)組

next數(shù)組實(shí)質(zhì)上就是找出模式串中前后字符重復(fù)出現(xiàn)的個數(shù)，為了能夠跳躍不可能匹配的步驟。
next數(shù)組的定義為：next[i]表示模式串A[0]至A[i]這個字串，使得前k個字符等于后k個字符的最大值，特別的k不能取i+i,因?yàn)樽执还膊舏+1個字符，自己跟自己相等毫無意義。

最終得到next數(shù)組為：

如何確定在移動過程中需要跳過多少步呢？下圖更直觀的體現(xiàn)了跳躍的過程：

對于上述紅色部分的計(jì)算跳過長度的公式為跳過的趟數(shù)=匹配上字符串中間字符長度-重復(fù)字符串長度

跳過這些步驟后并非再從頭開始匹配，而是從重復(fù)位置開始匹配：

最終，我們不難得出如下結(jié)論：

3python代碼實(shí)現(xiàn)

1.首先建立KMP對象，初始化參數(shù)：

2.建立next數(shù)組：

第一種最簡單的構(gòu)建方案，時間復(fù)雜度為O(m平法)：

第二種構(gòu)建方案，是一種遞推的方式進(jìn)行構(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]時，就可以直接向右擴(kuò)展了。

遞推構(gòu)建next數(shù)組代碼如下：

3.檢索過程代碼：

4.測試代碼：

作者原創(chuàng)，未經(jīng)授權(quán)請勿轉(zhuǎn)載

總結(jié)

以上是生活随笔為你收集整理的3算法全称_全网最通俗的KMP算法图解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。