KMP算法是一種改進(jìn)的字符串匹配算法亮靴，由D.E.Knuth，J.H.Morris和V.R.Pratt三人同時(shí)發(fā)現(xiàn)况既，因此人們稱(chēng)它為Knuth-Morris-Pratt算法（簡(jiǎn)稱(chēng)KMP）昼弟。KMP算法的關(guān)鍵是利用匹配失敗后的信息彭羹，盡量減少模式串與主串的匹配次數(shù)以達(dá)到快速匹配的目的。具體實(shí)現(xiàn)依賴(lài)一個(gè)next()函數(shù)岛啸，函數(shù)本身包含了模式串的局部匹配信息钓觉，其時(shí)間復(fù)雜度為O(m+n)。
網(wǎng)上有很多文章講解KMP算法坚踩，但都不夠清晰透徹荡灾、通俗易懂，尤其在介紹最令人困惑的next()函數(shù)時(shí)瞬铸，解釋拗口批幌，模棱兩可，讓讀者理解起來(lái)頗為費(fèi)勁嗓节。本人通過(guò)閱讀各路大神的學(xué)習(xí)筆記荧缘，汲取其中精華部分，并結(jié)合自我理解拦宣，帶你全面剖析KMP算法思想及實(shí)現(xiàn)截粗，希望對(duì)學(xué)習(xí)KMP算法仍有盲區(qū)和疑惑的同學(xué)有所幫助信姓。
KMP算法的原理
舉例來(lái)說(shuō)，有一個(gè)字符串”BBC ABCDAB ABCDABCDABDE”（稱(chēng)為主串）绸罗，我想知道意推，里面是否包含另一個(gè)字符串”ABCDABD”（稱(chēng)為模式串）？
1.首先从诲，主串”BBC ABCDAB ABCDABCDABDE”的第一個(gè)字符與模式串”ABCDABD”的第一個(gè)字符左痢，進(jìn)行比較。因?yàn)锽與A不匹配系洛，所以模式串需要后移一位俊性。
2.因?yàn)锽與A不匹配，模式串需要再往后移描扯。
3.就這樣定页，直到主串有一個(gè)字符，與模式串的第一個(gè)字符相同為止绽诚。
4.接著比較主串和模式串的下一個(gè)字符典徊，發(fā)現(xiàn)還是相同。
5.直到主串有一個(gè)字符恩够，與模式串對(duì)應(yīng)的字符不相同為止卒落，如下圖所示。
6.這時(shí)蜂桶，最自然的反應(yīng)是儡毕，將模式串整個(gè)后移一位，再?gòu)念^逐個(gè)比較扑媚。這樣做雖然可行腰湾，但是效率很差，因?yàn)槟阋选彼阉魑恢谩币频揭呀?jīng)比較過(guò)的位置疆股，重比一遍费坊。
7.一個(gè)基本事實(shí)是，當(dāng)空格與D不匹配時(shí)旬痹，你其實(shí)知道前面六個(gè)字符是”ABCDAB”附井。KMP算法的想法是，設(shè)法利用這個(gè)已知信息两残，不要把”搜索位置”移回已經(jīng)比較過(guò)的位置羡忘，繼續(xù)把它向后移，這樣就提高了效率磕昼。
8.怎么做到這一點(diǎn)呢卷雕？可以針對(duì)模式串，算出一張《部分匹配表》（Partial Match Table）票从。這張表是如何產(chǎn)生的漫雕，后面再介紹滨嘱，這里只要會(huì)用就可以了。
9.如下圖所示浸间，已知空格與D不匹配時(shí)太雨，前面六個(gè)字符”ABCDAB”是匹配的。查表可知魁蒜，”ABCDAB”中最后一個(gè)匹配字符B對(duì)應(yīng)的”部分匹配值”為2囊扳，因此按照下面的公式算出向后移動(dòng)的位數(shù)：
移動(dòng)位數(shù) = 已匹配的字符數(shù) - 對(duì)應(yīng)的部分匹配值
因?yàn)?6 - 2 等于4，所以將模式串整體向后移動(dòng)4位兜看。
10.如下圖锥咸，因?yàn)榭崭衽cＣ不匹配，模式串還要繼續(xù)往后移细移。這時(shí)搏予，已匹配的字符數(shù)為2（”AB”），對(duì)應(yīng)的”部分匹配值”為0弧轧。所以雪侥，移動(dòng)位數(shù) = 2 - 0，結(jié)果為 2精绎，于是將模式串向后移2位速缨。
11.如下圖所示，因?yàn)榭崭衽cA不匹配代乃，需要繼續(xù)后移一位鸟廓。
12.逐位比較，直到發(fā)現(xiàn)C與D不匹配襟己。于是，移動(dòng)位數(shù) = 6 - 2牍陌，繼續(xù)將模式串向后移動(dòng)4位擎浴。
13.逐位比較，直到模式串的最后一位毒涧，發(fā)現(xiàn)完全匹配贮预，于是搜索完成。如果還要繼續(xù)搜索（即找出全部匹配）契讲，移動(dòng)位數(shù) = 7 - 0仿吞，再將模式串向后移動(dòng)7位，這里就不再重復(fù)了捡偏。
部分匹配表
下面介紹《部分匹配表》是如何產(chǎn)生的唤冈。
首先，要了解兩個(gè)概念：”前綴”和”后綴”银伟。 “前綴”指除了最后一個(gè)字符以外你虹，一個(gè)字符串的全部頭部組合绘搞；”后綴”指除了第一個(gè)字符以外，一個(gè)字符串的全部尾部組合傅物。
“部分匹配值”就是”前綴”和”后綴”的最長(zhǎng)的共有元素的長(zhǎng)度夯辖。以”ABCDABD”為例，
- "A"的前綴和后綴都為空集董饰，共有元素的長(zhǎng)度為0蒿褂；
- "AB"的前綴為[A]，后綴為[B]卒暂，共有元素的長(zhǎng)度為0啄栓；
- "ABC"的前綴為[A, AB]，后綴為[BC, C]介却，共有元素的長(zhǎng)度0谴供；
- "ABCD"的前綴為[A, AB, ABC]，后綴為[BCD, CD, D]齿坷，共有元素的長(zhǎng)度為0桂肌；
- "ABCDA"的前綴為[A, AB, ABC, ABCD]，后綴為[BCDA, CDA, DA, A]永淌，共有元素為"A"崎场，長(zhǎng)度為1；
- "ABCDAB"的前綴為[A, AB, ABC, ABCD, ABCDA]遂蛀，后綴為[BCDAB, CDAB, DAB, AB, B]谭跨，共有元素為"AB"，長(zhǎng)度為2李滴；
- "ABCDABD"的前綴為[A, AB, ABC, ABCD, ABCDA, ABCDAB]螃宙，后綴為[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的長(zhǎng)度為0所坯。
按照定義谆扎，”ABCDAB”的部分匹配表即如下所示：
“部分匹配值”的實(shí)質(zhì)是，有時(shí)候芹助，字符串頭部和尾部會(huì)有重復(fù)堂湖。比如，”ABCDAB”之中有兩個(gè)”AB”状土，那么它的”部分匹配值”就是2（”AB”的長(zhǎng)度）无蜂。模式串移動(dòng)的時(shí)候，第一個(gè)”AB”向后移動(dòng)4位（字符串長(zhǎng)度-部分匹配值）蒙谓，就可以來(lái)到第二個(gè)”AB”的位置斥季。
理解next數(shù)組
理解KMP算法的核心和難點(diǎn)就是理解next數(shù)組的巧妙設(shè)計(jì)，下面我會(huì)重點(diǎn)解釋next數(shù)組的含義累驮。
next數(shù)組泻肯，又叫做“失配函數(shù)”渊迁，它是以下標(biāo) 0 開(kāi)始的數(shù)組，為了方便大家理解灶挟，給出如下圖示：
根據(jù) KMP 算法琉朽，在失配位會(huì)調(diào)用該位的 next 數(shù)組的值，下面我將詳細(xì)道出next數(shù)組的來(lái)龍去脈稚铣。
next[i]表示在失配位i之前的最長(zhǎng)公共前后綴的長(zhǎng)度箱叁。
首先，我們?nèi)≈耙呀?jīng)匹配的部分（即藍(lán)色的那部分Ｌ枰健）
我們?cè)谏厦嬲f(shuō)到“最長(zhǎng)公共前后綴”耕漱，體現(xiàn)到下圖所示的樣子。
next數(shù)組的作用是通過(guò)尋找最長(zhǎng)公共前后綴的部分抬伺，快速移動(dòng)模式串螟够，從而提高字符串匹配的效率，如下圖所示：
next[i]返回當(dāng)前位置i的最長(zhǎng)公共前后綴的長(zhǎng)度峡钓，假設(shè)為 len 妓笙。因?yàn)閿?shù)組是由 0 開(kāi)始的，所以 next 數(shù)組讓模式串的第 len 位與主串匹配就是拿最長(zhǎng)前綴之后的第 1 位與失配位重新匹配能岩，避免匹配串從頭開(kāi)始寞宫，如下圖所示。
如果上圖中的紅色位置依然匹配失效拉鹃，則需要對(duì)上圖中的綠色部分再次去求解它的最長(zhǎng)公共前后綴長(zhǎng)度（假設(shè)為len’）辈赋，然后繼續(xù)向右移動(dòng)模式串，讓模式串的第 len’ 位與主串的失配位重新進(jìn)行匹配膏燕，如果仍舊不匹配钥屈，則繼續(xù)以上過(guò)程操作。如下圖所示：
我們發(fā)現(xiàn)坝辫，當(dāng)發(fā)生失配的時(shí)候篷就，可以借助遞推的思想，根據(jù)已知的結(jié)果繼續(xù)求出當(dāng)前失配位之前的最長(zhǎng)公共前后綴的長(zhǎng)度阀溶，然后，繼續(xù)移動(dòng)模式串鸦泳，從而進(jìn)行新一輪的字符串匹配银锻。
解釋這么多，那么next數(shù)組究竟如何求出呢做鹰？
我們需要分兩種情況考慮击纬。
1.當(dāng)紅色部分相同（即S[k]==S[q]）時(shí)，則當(dāng)前 next 數(shù)組的值為上一次 next 的值加一（即next[q] = k++）钾麸，如上圖所示更振。
2.當(dāng)紅色部分不等的時(shí)候炕桨，則需要對(duì)綠色部分遞推求解 k’ = next[k-1]，然后再對(duì)新的 k’ 位置字符與 q 位置字符進(jìn)行匹配肯腕，如果相等献宫，則 next[q] = k’+1，否則实撒，執(zhí)行遞推匹配姊途，直到k’=0時(shí)遞推結(jié)束。比如知态，模式串“ABCABXABCABC”捷兰，最后一個(gè)字符C的next數(shù)組值為3。（因?yàn)镃之前的最長(zhǎng)公共前后綴為“ABCAB”负敏，而“ABCAB”的最長(zhǎng)公共前后綴為“AB”贡茅，其長(zhǎng)度為2，又源于第三個(gè)字符C與最后一個(gè)字符C匹配其做，所以最后一個(gè)字符C的next數(shù)組值為3）
代碼實(shí)現(xiàn)
創(chuàng)建文件kmp.c顶考，內(nèi)容如下：
#include<stdio.h>
#include<string.h>
void makeNext(const char P[],int next[])
{
int q,k;
int m = strlen(P);
next[0] = 0;
for (q = 1,k = 0; q < m; ++q)
{
while(k > 0 && P[q] != P[k])
k = next[k-1];
if (P[q] == P[k])
{
// 上一次的next值+1
k++;
}
next[q] = k;
}
}
void kmp(const char T[],const char P[],int next[])
{
int n,m;
int i,q;
n = strlen(T);
m = strlen(P);
makeNext(P,next);
for (i = 0,q = 0; i < n; ++i)
{
while(q > 0 && P[q] != T[i])
q = next[q-1];
if (P[q] == T[i])
{
q++;
}
if (q == m)
{
q=0;
printf("Pattern occurs with shift: %d\n",(i-m+1));
}
}
}
int main()
{
int i;
int next[20]={0};
char T[] = "BBC ABCDABD ABCDABCDABDE";
char P[] = "ABCDABD";
printf("主串：%s\n",T);
printf("模式串：%s\n",P );
kmp(T,P,next);
printf("next數(shù)組：");
for (i = 0; i < strlen(P); ++i)
{
printf("%d ",next[i]);
}
printf("\n");
return 0;
}
保存后，在終端執(zhí)行如下編譯命令：
$ gcc -o kmp kmp.c
$ ./kmp
# 其運(yùn)行結(jié)果如下：
主串：BBC ABCDABD ABCDABCDABDE
模式串：ABCDABD
Pattern occurs with shift: 4
Pattern occurs with shift: 16
next數(shù)組：0 0 0 0 1 2 0
總結(jié)
理解KMP算法的難點(diǎn)就在于理解next數(shù)組的實(shí)現(xiàn)庶柿，在遇到失配位時(shí)能夠靈活地應(yīng)用遞推方法村怪，根據(jù)已知的結(jié)果，進(jìn)一步求解出子最長(zhǎng)公共前后綴的長(zhǎng)度浮庐，然后進(jìn)一步的完成新一輪的匹配甚负，從而避免從頭開(kāi)始，極大提高了匹配速率审残。kmp算法的時(shí)間復(fù)雜度O(n+m)梭域，可以采用均攤分析來(lái)解答，具體可參考算法導(dǎo)論搅轿。
參考文章：
http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html 作者-阮一峰
http://www.tuicool.com/articles/e2Qbyyf
