了解KMP算法，應(yīng)從傳統(tǒng)暴力匹配算法的弊端入手，思考優(yōu)化方式，并進(jìn)行分析

傳統(tǒng)暴力法過(guò)程

用以下兩個(gè)字符串舉例：

S: abababaababacb
M: ababacb

查找S串是否包含子串，暴力解法思路為從S串的第一個(gè)字符開始匹配子串，如果不匹配，則從第二個(gè)字符重新開始，以此類推。過(guò)程如下：

算法實(shí)現(xiàn)如下：

顯然該方法的時(shí)間復(fù)雜度為O(mn)，其中m為主串S的長(zhǎng)度，n為子串M的長(zhǎng)度

KMP算法思路

反思暴力法，其最大的問(wèn)題就是每次都會(huì)將j指針重置，并將i指針移動(dòng)到上次匹配開頭的下一位，原本已經(jīng)匹配完的部分完全沒有發(fā)揮作用，造成了浪費(fèi)。
KMP算法的核心思想就是從已經(jīng)匹配的部分獲取信息，使i指針不進(jìn)行回溯
通過(guò)觀察第一次失敗時(shí)已經(jīng)匹配完成的串：ababa，我們可以發(fā)現(xiàn)它的前三個(gè)字符和最后三個(gè)字符是一樣的，即aba。因此，其實(shí)我們通過(guò)右移S串，將這兩個(gè)aba對(duì)齊，如下所示：

a b a b a b a a b a b a c b
?????a b a b a c b

這個(gè)操作對(duì)人類而言很好理解，但計(jì)算機(jī)要如何知道移動(dòng)多少距離呢？為了解決這個(gè)問(wèn)題，我們需要先認(rèn)識(shí)三個(gè)概念：

字符串的前綴、后綴和部分匹配值

字符串的前綴，指的是除了最后一個(gè)字符以外，該字符串的所有頭部子串；字符串的后綴則相反，指的是除了第一個(gè)字符以外，該字符的所有尾部子串；而部分匹配值，指的是字符串的前綴和后綴交集中長(zhǎng)度最大的子串。概念比較不直觀，下面我們以S:ababacb為例，了解這三個(gè)概念。

我們將字符串S分為長(zhǎng)度依次增加，均以S的第一個(gè)字符為開頭的子串集合：

并分別考察這些子串的前綴、后綴及部分匹配值：

1. a 的前后綴均為空集(因?yàn)榍昂缶Y均不包括對(duì)應(yīng)端點(diǎn))，交集也為空集，記部分匹配值為0

2. ab 的前綴為{a}，后綴為，交集為空集，部分匹配值為0

3. aba 的前綴為{a, ab}，后綴為{a, ba}，交集為{a}，長(zhǎng)度為1，因此部分匹配值為1

4. abab 的前綴為{a, ab, aba}，后綴為{b, ab, bab}，交集為{ab}，長(zhǎng)度為2，因此部分匹配值為2

5. ababa 的前綴為{a, ab, aba, abab}，后綴為{a, ba, aba, baba}，交集為{a, aba}，最長(zhǎng)元素的長(zhǎng)度為3，因此部分匹配值為3

6. ababac 的前綴為{a, ab, aba, abab, ababa}，后綴為{c, ac, bac, abac, babac}，交集為空集，因此部分匹配值為0

7. ababacb 的前綴為{a, ab, aba, abab, ababa, ababac}，后綴為{b, cb, acb, bacb, abacb, babacb}，交集為空集，因此部分匹配值為0

梳理完畢后，我們可以得到一個(gè)關(guān)于串S的部分匹配值表: [0, 1, 2, 3, 0, 0]，這個(gè)表在KMP算法中至關(guān)重要。

計(jì)算子串應(yīng)該右移的距離

我們回頭觀察第一次發(fā)生不匹配的情況：

觀察已經(jīng)匹配的這部分子串(標(biāo)綠部分)，即ababa，通過(guò)剛才的部分匹配值表，我們可以得到它最后一個(gè)字符的部分匹配值為3。從定義可知，這個(gè)值表示了ababa這個(gè)字符串擁有一個(gè)長(zhǎng)度為3的，相等的前綴和后綴，很顯然該字符串為aba。此時(shí)我們讓S串中的前綴aba與M串中的后綴aba對(duì)齊，如下圖所示：

此時(shí) i 指針之前的aba確定是匹配好的，因此不需要移動(dòng) i 指針。關(guān)于 j 指針的移動(dòng)將在下文介紹，此處我們考察S串右移的距離：

我們將已經(jīng)匹配完畢的字符串記為A，很顯然，我們的操作為將A中最長(zhǎng)的相同前后綴對(duì)齊，對(duì)齊方式為M串中A的后綴對(duì)齊S串中A的前綴，因此我們的移動(dòng)距離就應(yīng)該是：

我們不難發(fā)現(xiàn) length(A) = j，將部分匹配值表記為 next，我們可以得到如下關(guān)系式：

回溯 j 指針

在上述移動(dòng)S串后的圖中，很容易看出來(lái)我們需要將j指針移動(dòng)到i指針的正下方以便繼續(xù)進(jìn)行匹配，如下圖：

該位置其實(shí)就是S串去除掉A串后的第一個(gè)位置，因?yàn)榍懊嬉呀?jīng)可以確保完全匹配，因此從該位置繼續(xù)往下匹配即可。因此我們可以列出先前的j指針位置(j_old)和移動(dòng)后的j指針位置(j_new)的關(guān)系式：

通過(guò)以上式子，我們可以闡述出KMP算法的步驟：

1. 求出S串的next表

2. 使用i、j指針對(duì)M串與S串逐字匹配

3. 匹配，則i和j指針均向后移動(dòng)

4. 不匹配，i指針不動(dòng)，j指針置為next[j-1]

5. 重復(fù)2~4

基于以上思路，我們可以寫出KMP算法的代碼實(shí)現(xiàn)(假設(shè)我們已經(jīng)寫好了可以求next表的函數(shù)get_next)：

next表的求法

KMP算法核心為next表，我們需要高效地得到子串的next表，才能繼續(xù)執(zhí)行KMP算法。next表的計(jì)算方式主要有兩種，一種即為上述介紹next表概念時(shí)的手算法，下文主要介紹第二種。

仍以串Sababacb為例，我們觀察其next表獲得的過(guò)程

觀察next[0]，由于a的前后綴均為空集，所以next[0]必然為0
觀察next[1]，由于新增字符b與a不同，因此前后綴仍為空集，next[1]=0 觀察next[2]，觀察到新加入的a與第一個(gè)a可以產(chǎn)生一個(gè)相同的前后綴，長(zhǎng)度為1，所以next[2]=1，如圖所示：

觀察next[3]，加入了一個(gè)新的b，發(fā)現(xiàn)剛剛匹配的a后面也有一個(gè)b，他們可以組成更長(zhǎng)的前后綴，因此next[3]=next[2]+1=2，如圖所示：

觀察next[5]，此時(shí)c加入，無(wú)法繼續(xù)延長(zhǎng)前后綴，這種情況應(yīng)該怎么處理呢？

現(xiàn)在我們已經(jīng)掌握了第一個(gè)規(guī)律，即加入與之前相同的字符可以延長(zhǎng)前后綴的規(guī)律，我們以j代表next表的指針，我們分析：

“已經(jīng)找到的最長(zhǎng)前后綴中前綴的后一個(gè)字符"的位置，其實(shí)就是j-1位置的next值，因?yàn)閚ext[j-1]為串S的前j-1個(gè)字符的最長(zhǎng)相同前后綴的長(zhǎng)度，而他的下一個(gè)字符的下標(biāo)，就是next[j-1]

了解了這個(gè)規(guī)律后，我們用一個(gè)新的例子來(lái)幫助理解當(dāng)新加入的字符與前面不同時(shí)，即：

S[next[j-1]] != S[j]

時(shí)，應(yīng)該如何處理。

我們記串abacabab為B，先給出其next[0]~next[6]的值，如圖：

考察next[7]時(shí)，發(fā)現(xiàn)無(wú)法繼續(xù)組成更長(zhǎng)的前后綴了。因此我們應(yīng)該放棄“延長(zhǎng)最長(zhǎng)前后綴”的思路，去找找那些不是最長(zhǎng)的前后綴，是否可以進(jìn)行延長(zhǎng)。思路如下：

1. 我們需要考察b前面已經(jīng)找到的最長(zhǎng)前后綴里，是否可以和b組合延長(zhǎng)的前后綴，也就是在上圖標(biāo)橙的aba里找

2. 也就是將問(wèn)題轉(zhuǎn)化成向aba串中加入字符b，應(yīng)該如何計(jì)算其部分匹配值

3. 因此我們需要aba的next表，來(lái)嘗試是否可以重新利用規(guī)律1

4. 正巧，aba的next表在綠色的那一塊已經(jīng)完成了

我們可以發(fā)現(xiàn)這個(gè)已經(jīng)找到的最長(zhǎng)前后綴的長(zhǎng)度其實(shí)就等于next[j-1]。接下來(lái)我們嘗試?yán)靡?guī)律1

為了方便，我們令curr=next[j-1]，并得到完整的求next表函數(shù)：

至此KMP算法結(jié)束，在撰寫過(guò)程中筆者也深感知識(shí)儲(chǔ)備不足，難以用言語(yǔ)簡(jiǎn)單地表述清楚，寫下此篇主要為檢測(cè)自身掌握情況，并在未來(lái)做復(fù)習(xí)用