前言

在上一篇文章字符串匹配算法(一)——BF算法
提到過(guò)悯蝉，字符串匹配的思路是固定的：

1. 將模式串和主串進(jìn)行比較
   • 從前往后比較
   • 從后往前比較
2. 匹配時(shí)，比較主串和模式串的下一個(gè)位置
3. 失配時(shí),
   • 在模式串中尋找一個(gè)合適的位置
     • 如果找到恤溶，從這個(gè)位置開(kāi)始與主串當(dāng)前失配位置進(jìn)行比較
     • 如果未找到柏腻，從模式串的頭部與主串失配位置的下一個(gè)位置進(jìn)行比較
   • 在主串中找到一個(gè)合適的位置冯挎，重新與模式串進(jìn)行比較

優(yōu)化在于其中的步驟，而KMP算法莽囤，就是優(yōu)化第3步失配時(shí)尋找模式串合適位置的操作谬擦。

算法介紹和分析

那么如何尋找模式串中所謂合適的位置呢？可以先來(lái)看個(gè)栗子：

QQ20200114-214316.png

QQ20200114-214756.png

……

QQ20200114-215525.png

QQ20200114-220336.png

上面是 BF 匹配過(guò)程中從N_k到N_k+m的 m 次匹配過(guò)程朽缎，從中我們可以發(fā)現(xiàn)惨远，從第 k 步到第 k+m 步時(shí)谜悟，指針 i 和 j 又回到了相同的位置，且 第 k+m 步 更具有匹配的可能性北秽，所以我們思考一下葡幸，是不是可以由第 k 步直接跳到第 k+m 步呢？如果可以贺氓，就可以減少 m-1 次比較蔚叨，大大提升效率。再進(jìn)一步思考辙培，如果將整個(gè)匹配過(guò)程再看作是重復(fù)地由N_k直接到N_k+m的推進(jìn)蔑水，那么每次重復(fù)時(shí)，模式串開(kāi)始比較的位置就是我們所要找的合適的位置扬蕊。

如何尋找這些位置呢搀别？我們可以把這個(gè)問(wèn)題轉(zhuǎn)化為求next數(shù)組的過(guò)程。

求 next 數(shù)組

我們?cè)僮屑?xì)觀察下 N_k 和 N_k+m 兩個(gè)狀態(tài)

QQ20200114-214316.png

QQ20200114-220336.png

由于 N_k 狀態(tài)下厨相，模式串與主串具有完全匹配的部分领曼，且要達(dá)到 N_k+m 狀態(tài)所需移動(dòng)到的位置信息也存在于匹配的部分，因此我們可以無(wú)視掉主串蛮穿，只看模式串即可得到next數(shù)組。

再認(rèn)真觀察我們還能發(fā)現(xiàn)毁渗，N_k 狀態(tài)不匹配時(shí)践磅，N_k+m 狀態(tài)本質(zhì)上是將模式串中的另外一對(duì) AB 和 主串 達(dá)成之前的已匹配狀態(tài)。所以求next數(shù)組的問(wèn)題又可以轉(zhuǎn)化為當(dāng)m位置不匹配時(shí)灸异，求m位置之前的子串的最大相同前后綴的問(wèn)題府适。

首先要建立一個(gè)規(guī)則，具有前后綴的字符串長(zhǎng)度至少為2肺樟，所以我們定義如果長(zhǎng)度為0檐春，則對(duì)應(yīng)next數(shù)組值為-1，如果長(zhǎng)度為1么伯，值為0疟暖。下面舉個(gè)栗子：

ABABABD

QQ20200115-204949.png

手工求這么看其實(shí)沒(méi)什么難度，自己多寫(xiě)幾個(gè)串練一遍就會(huì)了田柔。

代碼

學(xué)會(huì)如何手工求next數(shù)組之后俐巴，整個(gè)KMP算法的代碼如何寫(xiě)呢？
還記得最開(kāi)始提到要記住的一點(diǎn)嗎硬爆？匹配思路是一樣的欣舵，只是優(yōu)化了失配后的操作。根據(jù)這一點(diǎn)缀磕，我們可以把BF算法的框架先搬過(guò)來(lái)：

carbon.png

這樣是不是可以接下來(lái)去補(bǔ)全 getNext() 方法就可以了呢缘圈？我們來(lái)看一個(gè)特殊情況：

QQ20200115-211138.png

QQ20200115-211437.png

當(dāng)處在N_k+m狀態(tài)時(shí)劣光，發(fā)現(xiàn)失配位置前的 AB 沒(méi)有最長(zhǎng)公共前后綴，于是只能退回到BF算法的做法糟把，也就是i++;j=0绢涡。但是這和我們上面的框架代碼不符，需要進(jìn)行改造：

• 每當(dāng) j = next[j] === -1時(shí)糊饱，也需要進(jìn)入第一個(gè)分支垂寥，使得 i++;j++(-1 + 1 = 0），變相達(dá)到效果另锋。

得到最終的框架代碼：

carbon的副本.png

接下來(lái)就是進(jìn)行對(duì)next數(shù)組的求解——完善 getNext()滞项。這時(shí)候有的同學(xué)可能就會(huì)想對(duì)上述手工求法進(jìn)行代碼轉(zhuǎn)化，可是萬(wàn)一模式串很長(zhǎng)的話夭坪，那么這個(gè)時(shí)間復(fù)雜度就會(huì)變得相當(dāng)?shù)母呶呐校孕枰捎玫ǎ妹看嗡玫慕Y(jié)果來(lái)求下一個(gè)結(jié)果室梅，從而拼湊出next數(shù)組戏仓。

我們假設(shè)某一時(shí)刻有一個(gè)狀態(tài)S_k

QQ20200116-214003.png

此時(shí)我們已經(jīng)求完了next[j]的值，如何去求next[j+1]呢亡鼠？仔細(xì)觀察狀態(tài)圖赏殃，發(fā)現(xiàn)：

• 若P_k === P_j，則 P_j+1 前有next[j] + 1 = 4個(gè)相同的前后綴 P₀P₁P_k-jP_k 和 P_j-kP_j-k+1P_j-1P_j间涵，也就是 next[j+1] = next[j] +1 = k + 1

再來(lái)看一個(gè)狀態(tài)

QQ20200118-151300.png

同樣是求完了next[j]的值仁热，

• 若P_k === P_j，對(duì)比 P_next[k] 是否 等于 P_j勾哩；如果 P_nextⁿ[k] === P_j抗蠢，則next[j+1] = P_nextⁿ[k] + 1 = k + 1

如果 P_nextⁿ[k] !== P_j呢？

QQ20200118-151336.png

可以看到思劳，

• 如果P_nextⁿ[k] !== P_j迅矛，則不斷地遞歸前綴索引 k = next[k] 直到回到前綴第一個(gè)位置，則表示沒(méi)有相同的前后綴潜叛，此時(shí) j = -1秽褒，則 next[j+1] = P_nextⁿ[k] + 1 = k + 1 = 0

根據(jù)以上分析，我們可以補(bǔ)充完 getNext()

carbon的副本2.png

再優(yōu)化一下寫(xiě)法

carbon的副本3.png

至此钠导，一個(gè)完整的KMP算法就寫(xiě)好了震嫉。

思考是否還有優(yōu)化的空間

我們來(lái)看一個(gè)特殊的例子：

QQ20200118-155025.png

這是一個(gè)前綴相同的一個(gè)模式串，且我們已經(jīng)求得了next數(shù)組牡属，接下來(lái)我們模擬一下上面寫(xiě)好的程序進(jìn)行的操作：

1. j = 5票堵，needle[5] !== haystack[i]；next[j] = 4逮栅，j = next[j];
2. j = 4悴势，needle[4] !== haystack[i]窗宇；next[j] = 3，j = next[j];
3. j = 3特纤，needle[3] !== haystack[i]军俊；next[j] = 2，j = next[j];
4. j = 2捧存，needle[2] !== haystack[i]粪躬；next[j] = 1，j = next[j];
5. j = 1昔穴，needle[1] !== haystack[i]镰官；next[j] = 0，j = next[j];
6. j = 0吗货，needle[0] !== haystack[i]泳唠；next[j] = -1，j = next[j];
7. j = -1, j++;i++;

我們發(fā)現(xiàn)由于前綴都是相等的宙搬，當(dāng)?shù)?步發(fā)現(xiàn)失配時(shí)笨腥，直接 j = -1 就可以了，也就是 next[5] = -1 即可勇垛。所以脖母，優(yōu)化點(diǎn)其實(shí)是體現(xiàn)在對(duì)next數(shù)組的優(yōu)化，我們稱(chēng)之為nextVal數(shù)組

求nextVal數(shù)組

如何求nextVal數(shù)組呢闲孤？我們還是以上面的特殊情況為例镶奉，看兩個(gè)狀態(tài)：

QQ20200118-163223.png

QQ20200118-164922.png

此時(shí)我們已經(jīng)求完了nextVal[j]的值，仔細(xì)觀察狀態(tài)圖崭放，發(fā)現(xiàn)：

• 根據(jù)求next數(shù)組的過(guò)程,next[j + 1] = k + 1
  • 若P_j+1 !== P_{next[j + 1]}，在P_{next[j + 1]}發(fā)生失配時(shí)鸽凶，只要跳到P_j+1就有可能解決失配問(wèn)題币砂，則此時(shí)的 nextVal[j + 1] = next[j + 1]即可
  • 若P_j+1 === P_{next[j + 1]}，在P_{next[j + 1]}發(fā)生失配時(shí)玻侥，跳到P_j+1就并不能解決失配問(wèn)題决摧，則此時(shí)應(yīng)該繼續(xù)回溯nextVal的next[j + 1]的位置上（由于是迭代求法，此時(shí)nextVal[next[j + 1]]上的值一定是通過(guò)nextVal[next²[j + 1]]求得了）凑兰，即 nextVal[j + 1] = nextVal[next[j + 1]]

可以在 getNext() 的基礎(chǔ)上得到以下代碼：

carbon的副本4.png

next數(shù)組現(xiàn)在就已經(jīng)是一個(gè)可有可無(wú)的工具人了掌桩，我們把去掉，得到下一版代碼：

carbon (1).png

再進(jìn)行以下優(yōu)化得到最終代碼：

carbon (2).png

總結(jié)

總的來(lái)說(shuō)姑食，KMP算法和BF算法的字符串匹配思路在大方向上是沒(méi)有區(qū)別的波岛，只是引入了一個(gè)next數(shù)組或nextVal數(shù)組來(lái)求得模式串中合適的位置。只要理解了這兩個(gè)數(shù)組的求法音半，也就基本理解了KMP算法则拷。

后記

“字符串匹配算法”是“重學(xué)數(shù)據(jù)結(jié)構(gòu)與算法”系列筆記：

• 字符串匹配算法(一)——BF算法
• 字符串匹配算法(二)——KMP算法
• 字符串匹配算法(三)——BM算法
• 字符串匹配算法(四)——Sunday算法