快速模式匹配算法，簡稱KMP 算法，是在 BF 算法基礎(chǔ)上改進得到的算法。學(xué)習(xí) BF 算法我們知道，該算法的實現(xiàn)過程就是 "傻瓜式" 地用模式串（假定為子串的串）與主串中的字符一一匹配，算法執(zhí)行效率不高。
KMP 算法不同，它的實現(xiàn)過程接近人為進行模式匹配的過程。例如，對主串 A（""）和模式串 B（"ABCE"）進行模式匹配，如果人為去判斷，僅需匹配兩次。
圖 1 第一次人為模式匹配
第一次如圖 1 所示，最終匹配失敗。但在本次匹配過程中，我們可以獲得一些信息，模式串中 "ABC" 都和主串對應(yīng)的字符相同，但模式串中字符 'A' 與 'B' 和 'C' 不同。
因此進行下次模式匹配時，沒有必要讓串 B 中的 'A' 與主串中的字符 'B' 和 'C' 一一匹配（它們絕不可能相同），而是直接去匹配失敗位置處的字符 'A' ，如圖 2 所示：
圖 2 第二次人為模式匹配
至此，匹配成功。若使用 BF 算法，則此模式匹配過程需要進行 4 次。
由此可以看出，每次匹配失敗后模式串移動的距離不一定是 1，某些情況下一次可移動多個位置，這就是 KMP 模式匹配算法。
那么，如何判斷匹配失敗后模式串向后移動的距離呢？
模式串移動距離的判斷每次模式匹配失敗后，計算模式串向后移動的距離是 KMP 算法中的核心部分。
其實，匹配失敗后模式串移動的距離和主串沒有關(guān)系，只與模式串本身有關(guān)系。
例如，我們將前面的模式串 B 改為 "ABCAE"c語音的模式匹配算法，則在第一次模式匹配失敗，由于匹配失敗位置模式串中字符 'E' 前面有兩個字符 'A'，因此，第二次模式匹配應(yīng)改為如圖 3 所示的位置：
圖 3 模式匹配過程示意圖
結(jié)合圖 1、圖 2 和圖 3 不難看出，模式串移動的距離只和自身有關(guān)系，和主串無關(guān)。換句話說，不論主串如何變換，只要給定模式串，則匹配失敗后移動的距離就已經(jīng)確定了。
不僅如此，模式串中任何一個字符都可能導(dǎo)致匹配失敗，因此串中每個字符都應(yīng)該對應(yīng)一個數(shù)字，用來表示匹配失敗后模式串移動的距離。
注意，這里要轉(zhuǎn)換一下思想，模式串向后移動等價于指針 j 前移，如圖 4 中的 a) 和 b)。換句話說，模式串后移相當(dāng)于對指針 j 重定位。
圖 4 模式串后移等價于 j 前移
因此，我們可以給每個模式串配備一個數(shù)組（例如 next[]），用于存儲模式串中每個字符對應(yīng)指針 j 重定向的位置（也就是存儲模式串的數(shù)組下標(biāo)），比如 j=3，則該字符匹配失敗后指針 j 指向模式串中第 3 個字符。
模式串中各字符對應(yīng) next 值的計算方式是，取該字符前面的字符串（不包含自己），其前綴字符串和后綴字符串相同字符的最大個數(shù)再 +1 就是該字符對應(yīng)的 next 值。
前綴字符串指的是位于模式串起始位置的字符串，例如模式串 "ABCD"，則 "A"、"AB"、"ABC" 以及 "ABCD" 都屬于前綴字符串；后綴字符串指的是位于串結(jié)尾處的字符串，還拿模式串 "ABCD" 來說，"D"、"CD"、"BCD" 和 "ABCD" 為后綴字符串。注意，模式串中第一個字符對應(yīng)的值為 0，第二個字符對應(yīng) 1 ，這是固定不變的（先這么認(rèn)為）。因此c語音的模式匹配算法，圖 3 的模式串 "ABCAE" 中，各字符對應(yīng)的 next 值如圖 5 所示：
圖 5 模式串對應(yīng)的 next 數(shù)組
從圖 5 中的數(shù)據(jù)可以看出，當(dāng)字符 'E' 匹配失敗時，指針 j 指向模式串?dāng)?shù)組中第 2 個字符，即 'B'，同之前講解的圖 3 不謀而合。
以上所講 next 數(shù)組的實現(xiàn)方式是為了讓大家對此數(shù)組的功能有一個初步的認(rèn)識。接下來學(xué)習(xí)如何用編程的思想實現(xiàn) next 數(shù)組。編程實現(xiàn) next 數(shù)組要解決的主要問題依然是 "如何計算每個字符前面前綴字符串和后綴字符串相同的個數(shù)"。
仔細觀察圖 5，為什么字符 'C' 對應(yīng)的 next 值為 1？因為字符串 "AB" 前綴字符串和后綴字符串相等個數(shù)為 0，0 + 1 = 1。那么，為什么字符 'E' 的 next 值為 2？因為緊挨著該字符之前的 'A' 與模式串開頭字符 'A' 相等，1 + 1 = 2。
如果圖 5 中模式串為 ""，則對應(yīng) next 數(shù)組應(yīng)為 [0,1,1,1,2,3]，為什么字符 'E' 的 next 值是 3 ？因為緊挨著該字符前面的 "AB" 與開頭的 "AB" 相等，2 + 1 =3。
因此，我們可以設(shè)計這樣一個算法，剛開始時令 j 指向模式串中第 1 個字符（j=1），i 指向第 2 個字符（i=2）。接下來，對每個字符做如下操作：
如果 i 和 j 指向的字符相等，則 i 后面第一個字符的 next 值為 j+1，同時 i 和 j 做自加 1 操作，為求下一個字符的 next 值做準(zhǔn)備，如圖 6 所示：
圖 6 i 和 j 指向字符相等
上圖中可以看到，字符 'a' 的 next 值為 j +1 = 2，同時 i 和 j 都做了加 1 操作（此時 j=2，i=3）。當(dāng)計算字符 'C' 的 next 值時，還是判斷 i 和 j 指向的字符是否相等，顯然相等，因此令該字符串的 next 值為 j + 1 = 3，同時 i 和 j 自加 1（此次 next 值的計算使用了上一次 j 的值）。如圖 7 所示：
圖 7 i 和 j 指向字符仍相等
如上圖所示，計算字符 'd' 的 next 時，i 和 j 指向的字符不相等（此時 j=3，i=4），這表明最長的前綴字符串 "aaa" 和后綴字符串 "aac" 不相等，接下來要判斷次長的前綴字符串 "aa" 和后綴字符串 "ac" 是否相等，這一步的實現(xiàn)可以用 j = next[j] 來實現(xiàn)（注意，next 數(shù)組從下標(biāo) 1 開始使用，舍棄 next[0] ），如圖 8 所示：
圖 8 執(zhí)行 j=next[j] 操作
從上圖可以看到，i 和 j 指向的字符又不相同，因此繼續(xù)做 j = next[j] 的操作，如圖 9 所示：
圖 9 繼續(xù)執(zhí)行 j=next[j] 的操作
此時，由于 j 和 i 指向的字符仍不相等，繼續(xù)執(zhí)行 j=next[j] 得到 j=0，這意味著字符 'd' 前的前綴字符串和后綴字符串相同個數(shù)為 0，因此如果字符 'd' 導(dǎo)致了模式匹配失敗，則模式串移動的距離只能是 1。
這里給出使用上述思想實現(xiàn) next 數(shù)組的 C 語言代碼：
void Next(char*T,int *next){next[1]=0;int i=1;int j=0;//next[2]=1 可以通過第一次循環(huán)直接得出while (i<strlen(T)) {if (j==0||T[i-1]==T[j-1]) {i++;j++;next[i]=j;}else{j=next[j];}}}代碼中 j=next[j] 的運用可以這樣理解，每個字符對應(yīng)的next值都可以表示該字符前 "同后綴字符串相同的前綴字符串最后一個字符所在的位置"，因此在每次匹配失敗后，都可以輕松找到次長前綴字符串的最后一個字符與該字符進行比較。Next函數(shù)的缺陷
圖 10 Next 函數(shù)的缺陷
例如，在圖 10a) 中，當(dāng)匹配失敗時，Next 函數(shù)會由圖 10b) 開始繼續(xù)進行模式匹配，但是從圖中可以看到，這樣做是沒有必要的，純屬浪費時間。
出現(xiàn)這種多余的操作，問題在當(dāng) T[i-1]==T[j-1] 成立時，沒有繼續(xù)對 i++ 和 j++ 后的 T[i-1] 和 T[j-1] 的值做判斷。改進后的 Next 函數(shù)如下所示：
void Next(char*T,int *next){next[1]=0;int i=1;int j=0;while (iif (j==0||T[i-1]==T[j-1]) {i++;j++;if (T[i-1]!=T[j-1]) {next[i]=j;}else{next[i]=next[j];}}else{j=next[j];}}}注意，這里只設(shè)定了 next[1] 的值為 0，而 next[1] 的值，需要經(jīng)過判斷之后，才能最終得出，所以它的值不一定是 1。
使用精簡過后的 next 數(shù)組在解決例如模式串為 "" 這類的問題上，會大大提高效率，如圖 11 所示，精簡前為 next1，精簡后為 next2：
圖 11 改進后的 Next 函數(shù)KMP 算法的實現(xiàn)假設(shè)主串 A 為 ""，模式串 B 為 "abcac"，則 KMP 算法執(zhí)行過程為：
很明顯，使用 KMP 算法只需匹配 3 次，而同樣的問題使用 BF 算法則需匹配 6 次才能完成。
KMP 算法的完整 C 語言實現(xiàn)代碼為：
運行結(jié)果為： //調(diào)用了普通求 next 的方式，這里并未直接對 next[1] 賦值為 1，但通過函數(shù)第一次運行，也可以得出它的值為 1void Next(char*T,int *next){int i=1;next[1]=0;int j=0;while (i<strlen(T)) {if (j==0||T[i-1]==T[j-1]) {i++;j++;next[i]=j;}else{j=next[j];}}}int KMP(char * S,char * T){int next[10];Next(T,next);//根據(jù)模式串T,初始化next數(shù)組int i=1;int j=1;while (i<=strlen(S)&&j<=strlen(T)) {//j==0:代表模式串的第一個字符就和當(dāng)前測試的字符不相等；S[i-1]==T[j-1],如果對應(yīng)位置字符相等，兩種情況下，指向當(dāng)前測試的兩個指針下標(biāo)i和j都向后移if (j==0 || S[i-1]==T[j-1]) {i++;j++;}else{j=next[j];//如果測試的兩個字符不相等，i不動，j變?yōu)楫?dāng)前測試字符串的next值}}if (j>strlen(T)) {//如果條件為真，說明匹配成功return i-(int)strlen(T);}return -1;}int main() {int i=KMP("ababcabcacbab","abcac");printf("%d",i);return 0;}6