KMP算法是一種改進(jìn)的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt三人同時(shí)發(fā)現(xiàn)，因此人們稱它為Knuth-Morris-Pratt算法（簡(jiǎn)稱KMP）。KMP算法的關(guān)鍵是利用匹配失敗后的信息，盡量減少模式串與主串的匹配次數(shù)以達(dá)到快速匹配的目的。具體實(shí)現(xiàn)依賴一個(gè)next()函數(shù)，函數(shù)本身包含了模式串的局部匹配信息，其時(shí)間復(fù)雜度為O(m+n)。
網(wǎng)上有很多文章講解KMP算法，但都不夠清晰透徹、通俗易懂，尤其在介紹最令人困惑的next()函數(shù)時(shí)，解釋拗口，模棱兩可，讓讀者理解起來頗為費(fèi)勁。本人通過閱讀各路大神的學(xué)習(xí)筆記，汲取其中精華部分，并結(jié)合自我理解，帶你全面剖析KMP算法思想及實(shí)現(xiàn)，希望對(duì)學(xué)習(xí)KMP算法仍有盲區(qū)和疑惑的同學(xué)有所幫助。
KMP算法的原理
舉例來說，有一個(gè)字符串”BBC ABCDAB ABCDABCDABDE”（稱為主串），我想知道，里面是否包含另一個(gè)字符串”ABCDABD”（稱為模式串）？
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)比較過的位置，重比一遍。
7.一個(gè)基本事實(shí)是，當(dāng)空格與D不匹配時(shí)，你其實(shí)知道前面六個(gè)字符是”ABCDAB”。KMP算法的想法是，設(shè)法利用這個(gè)已知信息，不要把”搜索位置”移回已經(jīng)比較過的位置，繼續(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)度-部分匹配值），就可以來到第二個(gè)”AB”的位置。
理解next數(shù)組
理解KMP算法的核心和難點(diǎn)就是理解next數(shù)組的巧妙設(shè)計(jì)，下面我會(huì)重點(diǎn)解釋next數(shù)組的含義。
next數(shù)組，又叫做“失配函數(shù)”，它是以下標(biāo) 0 開始的數(shù)組，為了方便大家理解，給出如下圖示：
根據(jù) KMP 算法，在失配位會(huì)調(diào)用該位的 next 數(shù)組的值，下面我將詳細(xì)道出next數(shù)組的來龍去脈。
next[i]表示在失配位i之前的最長(zhǎng)公共前后綴的長(zhǎng)度。
首先，我們?nèi)≈耙呀?jīng)匹配的部分（即藍(lán)色的那部分?。?/p>
我們?cè)谏厦嬲f到“最長(zhǎng)公共前后綴”，體現(xiàn)到下圖所示的樣子。
next數(shù)組的作用是通過尋找最長(zhǎng)公共前后綴的部分，快速移動(dòng)模式串，從而提高字符串匹配的效率，如下圖所示：
next[i]返回當(dāng)前位置i的最長(zhǎng)公共前后綴的長(zhǎng)度，假設(shè)為 len 。因?yàn)閿?shù)組是由 0 開始的，所以 next 數(shù)組讓模式串的第 len 位與主串匹配就是拿最長(zhǎng)前綴之后的第 1 位與失配位重新匹配，避免匹配串從頭開始，如下圖所示。
如果上圖中的紅色位置依然匹配失效，則需要對(duì)上圖中的綠色部分再次去求解它的最長(zhǎng)公共前后綴長(zhǎng)度（假設(shè)為len’），然后繼續(xù)向右移動(dòng)模式串，讓模式串的第 len’ 位與主串的失配位重新進(jìn)行匹配，如果仍舊不匹配，則繼續(xù)以上過程操作。如下圖所示：
我們發(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)一步的完成新一輪的匹配，從而避免從頭開始，極大提高了匹配速率。kmp算法的時(shí)間復(fù)雜度O(n+m)，可以采用均攤分析來解答，具體可參考算法導(dǎo)論。
參考文章：
http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html 作者-阮一峰
http://www.tuicool.com/articles/e2Qbyyf
