?

轉(zhuǎn)載請(qǐng)注明來(lái)源，并包含相關(guān)鏈接。

?

網(wǎng)上有很多講解KMP算法的博客，我就不浪費(fèi)時(shí)間再寫(xiě)一份了。直接推薦一個(gè)當(dāng)初我入門(mén)時(shí)看的博客吧： http://www.cnblogs.com/yjiyjige/p/3263858.html 這位同學(xué)用詳細(xì)的圖文模式講解了KMP算法，非常適合入門(mén)。 ----------------------------------------------------------------------------------------------

KMP的next數(shù)組求法是很不容易搞清楚的一部分，也是最重要的一部分。我這篇文章就以我自己的感悟來(lái)慢慢推導(dǎo)一下吧！保證你看完過(guò)后是知其然，也知其所以然。

如果你還不知道KMP是什么，請(qǐng)先閱讀上面的鏈接，先搞懂KMP是要干什么。 下面我們就來(lái)說(shuō)說(shuō)KMP的next數(shù)組求法。 KMP的next數(shù)組簡(jiǎn)單來(lái)說(shuō)，假設(shè)有兩個(gè)字符串，一個(gè)是待匹配的字符串strText,一個(gè)是要查找的關(guān)鍵字strKey?，F(xiàn)在我們要在strText中去查找是否包含strKey，用i來(lái)表示strText遍歷到了哪個(gè)字符，用j來(lái)表示strKey匹配到了哪個(gè)字符。 如果是暴力的查找方法，當(dāng)strText[i]和strKey[j]匹配失敗的時(shí)候，i和j都要回退，然后從i-j的下一個(gè)字符開(kāi)始重新匹配。 而KMP就是保證i永遠(yuǎn)不回退，只回退j來(lái)使得匹配效率有所提升。它用的方法就是利用strKey在失配的j為之前的成功匹配的子串的特征來(lái)尋找j應(yīng)該回退的位置。而這個(gè)子串的特征就是前后綴的相同程度。 所以next數(shù)組其實(shí)就是查找strKey中每一位前面的子串的前后綴有多少位匹配，從而決定j失配時(shí)應(yīng)該回退到哪個(gè)位置。

我知道上面那段廢話很難懂，下面我們看一個(gè)彩圖：

這個(gè)圖畫(huà)的就是strKey這個(gè)要查找的關(guān)鍵字字符串。假設(shè)我們有一個(gè)空的next數(shù)組，我們的工作就是要在這個(gè)next數(shù)組中填值。 下面我們用數(shù)學(xué)歸納法來(lái)解決這個(gè)填值的問(wèn)題。 這里我們借鑒數(shù)學(xué)歸納法的三個(gè)步驟（或者說(shuō)是動(dòng)態(tài)規(guī)劃？）： 1、初始狀態(tài) 2、假設(shè)第j位以及第j位之前的我們都填完了 3、推論第j+1位該怎么填

初始狀態(tài)我們稍后再說(shuō)，我們這里直接假設(shè)第j位以及第j位之前的我們都填完了。也就是說(shuō)，從上圖來(lái)看，我們有如下已知條件： next[j] == k; next[k] == 綠色色塊所在的索引; next[綠色色塊所在的索引] == 黃色色塊所在的索引; 這里要做一個(gè)說(shuō)明：圖上的色塊大小是一樣的（沒(méi)騙我？好吧，請(qǐng)忽略色塊大小，色塊只是代表數(shù)組中的一位）。

我們來(lái)看下面一個(gè)圖，可以得到更多的信息：

1.由"next[j] == k;"這個(gè)條件，我們可以得到A1子串 == A2子串（根據(jù)next數(shù)組的定義，前后綴那個(gè)）。

2.由"next[k] == 綠色色塊所在的索引;"這個(gè)條件，我們可以得到B1子串 == B2子串。

3.由"next[綠色色塊所在的索引] == 黃色色塊所在的索引;"這個(gè)條件，我們可以得到C1子串 == C2子串。

4.由1和2(A1 == A2，B1 == B2)可以得到B1 == B2 == B3。

5.由2和3(B1 == B2， C1 == C2)可以得到C1 == C2 == C3。

6.B2 == B3可以得到C3 == C4 == C1 == C2

上面這個(gè)就是很簡(jiǎn)單的幾何數(shù)學(xué)，仔細(xì)看看都能看懂的。我這里用相同顏色的線段表示完全相同的子數(shù)組，方便觀察。

?

接下來(lái)，我們開(kāi)始用上面得到的條件來(lái)推導(dǎo)如果第j+1位失配時(shí)，我們應(yīng)該填寫(xiě)next[j+1]為多少？

next[j+1]即是找strKey從0到j(luò)這個(gè)子串的最大前后綴：

#：(#:在這里是個(gè)標(biāo)記，后面會(huì)用)我們已知A1 == A2，那么A1和A2分別往后增加一個(gè)字符后是否還相等呢？我們得分情況討論：

(1)如果str[k] == str[j]，很明顯，我們的next[j+1]就直接等于k+1。

　　用代碼來(lái)寫(xiě)就是next[++j] = ++k;

(2)如果str[k] != str[j]，那么我們只能從已知的，除了A1，A2之外，最長(zhǎng)的B1，B3這個(gè)前后綴來(lái)做文章了。

那么B1和B3分別往后增加一個(gè)字符后是否還相等呢？

由于next[k] == 綠色色塊所在的索引，我們先讓k = next[k]，把k挪到綠色色塊的位置，這樣我們就可以遞歸調(diào)用"#："標(biāo)記處的邏輯了。

?

由于j+1位之前的next數(shù)組我們都是假設(shè)已經(jīng)求出來(lái)了的，因此，上面這個(gè)遞歸總會(huì)結(jié)束，從而得到next[j+1]的值。

?

我們唯一欠缺的就是初始條件了：

next[0] = -1,? k = -1, j = 0

另外有個(gè)特殊情況是k為-1時(shí)，不能繼續(xù)遞歸了，此時(shí)next[j+1]應(yīng)該等于0，即把j回退到首位。

即 next[j+1] = 0; 也可以寫(xiě)成next[++j] = ++k;

?

public static int[] getNext(String ps) {char[] strKey = ps.toCharArray(); int[] next = new int[strKey.length]; // 初始條件 int j = 0; int k = -1; next[0] = -1; // 根據(jù)已知的前j位推測(cè)第j+1位 while (j < strKey.length - 1) { if (k == -1 || strKey[j] == strKey[k]) { next[++j] = ++k; } else { k = next[k]; } } return next; }

?

現(xiàn)在再看這段代碼應(yīng)該沒(méi)有任何問(wèn)題了吧。

優(yōu)化：

細(xì)心的朋友應(yīng)該發(fā)現(xiàn)了，上面有這樣一句話：

(1)如果str[k] == str[j]，很明顯，我們的next[j+1]就直接等于k+1。用代碼來(lái)寫(xiě)就是next[++j] = ++k;

可是我們知道，第j+1位是失配了的，如果我們回退j后，發(fā)現(xiàn)新的j(也就是此時(shí)的++k那位)跟回退之前的j也相等的話，必然也是失配。所以還得繼續(xù)往前回退。

public static int[] getNext(String ps) {char[] strKey = ps.toCharArray(); int[] next = new int[strKey.length]; // 初始條件 int j = 0; int k = -1; next[0] = -1; // 根據(jù)已知的前j位推測(cè)第j+1位 while (j < strKey.length - 1) { if (k == -1 || strKey[j] == strKey[k]) { // 如果str[j + 1] == str[k + 1]，回退后仍然失配，所以要繼續(xù)回退 if (str[j + 1] == str[k + 1]) { next[++j] = next[++k]; } else { next[++j] = ++k; } } else { k = next[k]; } } return next; }

好了，自此KMP的next求法全部講解完畢。歡迎大家指出文章的錯(cuò)誤，我好更加完善它。

----------------------------------------------------------------------------------------------------------

下面說(shuō)說(shuō)面試的時(shí)候，給一個(gè)字符串，要你寫(xiě)出它的Next數(shù)組，應(yīng)該怎么寫(xiě)：

①：先對(duì)每一位左邊的子串求出最大前后綴串的長(zhǎng)度，作為初始的Next數(shù)組

②：因?yàn)榈谝晃皇鋾r(shí)需要移動(dòng)i，因此賦值為-1

③：P[3] == A, Next[3] == 0, P[0] == A;? 所以P[3] == P[0], (移動(dòng)過(guò)去后還是失配,需要繼續(xù)移動(dòng)),優(yōu)化Next[3]為Next[0],即-1

④：同理優(yōu)化Next[10]為Next[0],即-1

⑤：同理優(yōu)化P[14],P[15],P[16]

http://www.cnblogs.com/tangzhengyue/p/4315393.html

?

總結(jié)

以上是生活随笔為你收集整理的KMP算法的Next数组详解（转）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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