這篇文章用于總結(jié)自己對KMP算法的一些理解，如有錯誤，請不吝指出。

KMP算法用于字符串匹配加快進(jìn)程。

例如對于以下問題：

在字符串ABAACCABD中查找是否含有ABD這個串？

對于這個問題，很快就可以想到直接暴力搜索，多個循環(huán)依次匹配字符來達(dá)到目的，這種方法雖然簡單易懂，但是效率很低。應(yīng)用KMP算法可以有效地提高字符串匹配的效率。簡單來說KMP算法是利用了已經(jīng)匹配過的字符的信息來加快匹配的進(jìn)程。例如

ABAACCABD

|? |? |

ABD

當(dāng)檢索到第三位時，A與D并不匹配，暴力算法會直接將字串從第二格開始重新檢索，但是在KMP算法中會試圖利用第一位的A與第二位的B互相已經(jīng)匹配的信息來跳過一些不必要的步驟，已到達(dá)加速的目的。我個人認(rèn)為實(shí)際上是利用了字符串中的回文（好像也不是），在詳細(xì)解釋KMP算法是如何利用這些信息加速之前，首先我們需要了解字符串前綴和后綴的概念。

對于任何一個字符串，我們可以提取出它的前綴和后綴，例如對于ABABC這個字符串

ABABC

前綴： ABAB，ABA,AB, A

后綴： BABC, ABC, BC, C

通過這個例子，相信不難看出前綴和后綴的規(guī)律，實(shí)際上類似于包含第一個/最后一個字符的字串。KMP算法實(shí)際上就是對最長公共前后綴的一個利用。公共前后綴就是指前綴和后綴中相等的一部分，例如：

ABAB

前綴: ABA,AB,A

后綴 BAB,AB,B

那么ABAB的最長公共前后綴就是AB，KMP算法的核心之一就是如何找到最長公共前后綴，這里先按下不講，先解釋如何利用最長公共前后綴來加快匹配的進(jìn)程。

ABABAAAAACABABC

|? |? |? | ？

ABABC

對于這個兩個字符串，公共前后綴已經(jīng)標(biāo)注成了紅色，首先我們還是依次匹配，前面的ABAB都是完全相等的，知道第五位的A 與C不匹配，暴力算法會將ABABC向右移一位重新循環(huán)，從第一位開始繼續(xù)匹配，KMP算法則會直接右移兩位從第五位開始。（這里的第幾位指的是主串中的位置）

ABABAAAAACABABC? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

? ?|??

? ?ABABC

? ? ?暴力算法

ABABAAAAACABABC

? ? ? ? ? ?|??

? ? ?ABABC

? ? ?KMP算法

原因就在于在KMP算法中，我們已經(jīng)得出了字串的公共前后綴AB，也就是在字串中一定存在一個前面AB = 后面的AB。在和主串匹配的過程中，因?yàn)锳BABC中的ABAB部分是和主串中的前四位完全相等的，那么也就意味著主串之中也一定有一個前面AB=后面的AB，而實(shí)際上第一次匹配的過程中正式主串的前綴AB=字串的前綴AB，主串的后綴AB=字串的后綴AB。如下圖所示：

ABABAAAAACABABC??

ABABC

KMP算法的做法就是，直接用字串的前綴AB去對主串的后綴AB

ABABAAAAACABABC??

? ? ?ABABC

因?yàn)樽执那熬YAB=字串的后綴AB，字串的前綴AB又等于主串的前綴AB，那么顯而易見字串的前綴AB也等于主串的后綴AB，而且由于我們已知它們相等，就不用從主串的第三位開始匹配，直接跳過后綴AB到主串的第五位A進(jìn)行比較即可。我剛開始了解的其中一個疑惑時，這樣跳不會漏掉中間的字符導(dǎo)致結(jié)果不對嗎？這里我自己的想法是，實(shí)際上得出公共前后綴的過程已經(jīng)排查了漏掉的情況，因?yàn)槟康氖侨フ彝耆嗤淖址?，那么必須要保證所有的字符都相同，得到了最大的公共前后綴，也就意味著主串后面存在某一段字符串和字串中的前綴完全相同，當(dāng)遇到不匹配的字符之后，只需要直接將字串的前綴挪到主串的后綴即可。（這段比較亂，隨意看看即可）

接下來再看一個類似的例子，還是ABABC

ABACAAAAACABABC

|? |? |??

BBABC

在這個例子中，第四位就已經(jīng)不匹配了，我們應(yīng)該根據(jù)ABA這個字符串的公共前后綴來計算，也就是A，那么只需要將ABABC挪到如下位置即可：

ABACAAAAACABABC

? ? ? |??

? ? ? ABABC

那么對于我們想要查找的ABABC這個字符串，我們應(yīng)該分別計算出它每一個字串的最長公共前后綴的長度即，

A 0

AB 0

ABA 1

ABAB 2

ABABC 0

我們把得到的這組數(shù)字成為最長長度表：

ABABC

0 01 20

根據(jù)這組數(shù)字，將在最前方插入-1就得到了Nxet數(shù)組用來指引字串的下一位置即

ABACAAAAACABABC

|? |? |??

ABABC

-1001?2

當(dāng)?shù)谒奈坏腃與B不匹配時，Next數(shù)組的值為1，我們只需要將字串中的第一位（從第零位開始計算）移動C的位置即可，也就是

ABACAAAAACABABC

? ? ??|??

? ? ??ABABC

? ? ??-100 1?2

然后C與B還是不匹配，根據(jù)Next數(shù)組，將第零位移動到這個位置。當(dāng)Next數(shù)組等于-1時，直接將字串往后推一位。

ABACAAAAACABABC

? ? ? ? ?

? ? ? ??ABABC

? ? ? ?-100?1?2

以上就是KMP算法如何利用Next數(shù)組加速匹配過程，然后繼續(xù)介紹如何在字串中求得Next數(shù)組。

對于任意一個我們想要搜尋的字符串，首先我們需要求得該字符串每個字串的最長公共前后綴長度的數(shù)組，并根據(jù)這個數(shù)組找出Next數(shù)組。任然舉ABABC這個例子

ABABC

當(dāng)我們求A的最長公共前后綴長度時，顯而易見，應(yīng)該是0，因?yàn)樗麤]有任何字串，由此可以類推，所有字符串的長度數(shù)組L[0] = 0(用L表示長度數(shù)組，用N表示Next數(shù)組).

關(guān)鍵是如何求得任意一個L[K]的值，首先L[K]的值最多等于L[K-1]的值+1，因?yàn)樵谝阎狶[K-1]的最長公共前后綴長度，新加一個字符，那么最多就是直接相等，這種情況如下下圖

ABAB？

已知ABAB的最長公共前后綴長度為2，即AB，當(dāng)我們求ABAB?的公共前后綴時，只需要首先考慮前綴AB加上后面一位字符A是否等于后綴AB+后面一位字符？即ABA == AB？嗎，如果此時？的位置是A，那么我們很快就可以得出ABABA的最長公共前后綴為3。以此類推當(dāng)我們計算L[K]時首先比較L[K-1]的前綴+后一位字符是否等于L[K-1]的后綴+新的字符，如果相等L[K]=L[K-1]+1.這是最簡單的一種情況。第二種情況就是不相等

ABAB?? ?如果此時?等于B，那么就不滿足上述情況了，為了便于理解，我舉一個更長的字符串當(dāng)例子。

ABABABABB

對于這個字符串，不難看出他的前八位最長公共前后綴為ABAB，四位，現(xiàn)在我們要求第九位的最長公共前后綴長度。

ABABABAB？

為了便于理解，將前八位的前綴和后綴分別標(biāo)注出來，此時當(dāng)？= B那么不滿足上述說的第一種情況，但是我們可以發(fā)現(xiàn)實(shí)際上第一種方法可以總結(jié)為 前綴+后一位字符是否 == 后綴+新字符，如果相等則長度+1就是結(jié)果。

ABABABAB？

即使不滿足上述情況，因?yàn)榍熬Y字符串等于后綴字符串，也就意味著前綴的前綴字符串，等于后綴的后綴字符串。如上圖所示 紅綠色AB表示前綴ABAB的前后綴，藍(lán)黃色AB為后綴ABAB的前后綴，此時我們只需要再次驗(yàn)證紅色前綴AB+后一位字符是否等于黃色前綴AB+新字符如果相等，那么第九位公共前后綴長度就應(yīng)該等于ABAB的最長公共前后綴長度+1，如果不等，那么重復(fù)上述過程，直到前面的字符串公共前綴長度為0，那么所求的公共前后綴長度也等于0.回到舉得第一個例子

ABAB？

如果？不等于A，那么則繼續(xù)看前綴AB的公共前后綴，顯而易見應(yīng)該是0，那么ABAB？的公共前后綴長度就等于0. 最后在L數(shù)組的最前方插入-1就等于Next數(shù)組了。

以上是個人對于KMP算法一點(diǎn)總結(jié)，語言混亂，如有錯誤，請不吝指出。