樸素模式匹配算法的最大問題就是太低效了。于是三位前輩發(fā)表了一種KMP算法，其中三個字母分別是這三個人名的首字母大寫。
簡單的說，KMP算法的對于主串的當前位置不回溯。也就是說，如果主串某次比較時，當前下標為i,i之前的字符和子串對應的字符匹配，那么不要再像樸素算法那樣將主串的下標回溯，比如主串為“abcababcabcabcabcabc”,子串為“abcabx”.第一次匹配的時候，主串1,2,3,4,5字符都和子串相應的匹配，第6為‘c'與子串中的‘x'不匹配，說明此時i=6,下次匹配的時候，就不用再像樸素那樣，將i置為2，再循環(huán)置為3,4,5去和子串匹配了。而是直接從i=6(以i=6為開頭)開始和子串去進行匹配。
那么子串的下標的變化呢，是不是每次要從第一位開始去和主串匹配，實際上也不需要。還是上面的例子，第一次匹配后，子串的當前位置（下標）為j=6,因為前兩位a,b和主串的4,5位的a,b已經(jīng)比較完成，是匹配的，所以這兩位也無需比較，也就是從j=3開始和主串匹配。現(xiàn)在的問題是，如何找到子串的下標j的變化。
我們把子串各個位置的j值得變化定義為1個數(shù)組next，那么next的長度就是T串的長度。于是可以得到下面的函數(shù)定義：
上圖引用自《大話數(shù)據(jù)結(jié)構(gòu)》，關(guān)于更多的KMP算法的說明，尤其是next[j]的推導，讀者可以參考該書，講解的非常的詳細。下面給出該算法的java實現(xiàn)。
在《大話數(shù)據(jù)結(jié)構(gòu)》，保存串的數(shù)組的首位，也就是0下標位置保存的是字符串的長度。但是上面的next[j]卻可取值為0,這點我沒有弄明白，如有哪位牛人能幫忙解釋，萬分感謝。下面編寫的代碼略有不同，在0下標位置不再是保存字符串的長度，而是保存字符串的首字符，也就是是與字符串對應的。所以next[j]的計算函數(shù)也不太一樣,如下：
實現(xiàn)的代碼：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
|
public class Pattern_KMP { public static void main(String args[]) { int times; String source="abcabaabcabcabxxzhabaabcabcabxad"; String subStr="abcabx"; times=pattren_KMP(source, subStr); System.out.println("匹配次數(shù)："+times); } static int pattren_KMP(String source,String subStr) { int len1,len2; len1=source.length(); len2=subStr.length(); int i,j; i=j=0; int times=0; while(i<len1) { if(source.charAt(i)==subStr.charAt(j)) { i++; j++; }else { if(j==0)/*這一步很重要，如果沒有會進入死循環(huán)，也就是，如果主串某位與子串*/ i++;/*第一位不等的話，必須往后移位。*/ j=next(subStr,j); } if(j==len2) { times++; j=0; } } return times; } static int next(String subStr,int j) { if(j==0) return 0; else { int next=0; int k=1; int m1; int m2; int i,n; /*這一循環(huán)對應實現(xiàn)上面函數(shù)的第二項*/ while(k<j) { String sub1="",sub2=""; for(m1=0,m2=j-k;m1<k&&m2<j;m1++,m2++) { sub1+=subStr.charAt(m1); sub2+=subStr.charAt(m2); } for(i=0,n=0;i<sub1.length()&&n<sub2.length();i++,n++) { if(sub1.charAt(i)!=sub2.charAt(n)) break; } if(i==sub1.length()&&n==sub2.length()) next=k; k++; } return next; } } } |
下面附上《大話數(shù)據(jù)結(jié)構(gòu)》中的KMP算法（c代碼）供對照參考（不是完整可執(zhí)行程序）
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
/* 通過計算返回子串T的next數(shù)組。 */void get_next(String T, int *next) { int i,j; i=1; j=0; next[1]=0; while (i<T[0]) /* 此處T[0]表示串T的長度 */ { if(j==0 || T[i]== T[j]) /* T[i]表示后綴的單個字符，T[j]表示前綴的單個字符 */ { ++i; ++j; next[i] = j; } else j= next[j]; /* 若字符不相同，則j值回溯 */ } } /* 返回子串T在主串S中第pos個字符之后的位置。若不存在，則函數(shù)返回值為0。 *//* T非空，1≤pos≤StrLength(S)。 */int Index_KMP(String S, String T, int pos) { int i = pos; /* i用于主串S中當前位置下標值，若pos不為1，則從pos位置開始匹配 */ int j = 1; /* j用于子串T中當前位置下標值 */ int next[255]; /* 定義一next數(shù)組 */ get_next(T, next); /* 對串T作分析，得到next數(shù)組 */ while (i <= S[0] && j <= T[0]) /* 若i小于S的長度并且j小于T的長度時，循環(huán)繼續(xù) */ { if (j==0 || S[i] == T[j]) /* 兩字母相等則繼續(xù)，與樸素算法增加了j=0判斷 */ { ++i; ++j; } else /* 指針后退重新開始匹配 */ j = next[j];/* j退回合適的位置，i值不變 */ } if (j > T[0]) return i-T[0]; else return 0; } |
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
原文鏈接：http://blog.csdn.net/Allenalex/article/details/11726107
