D.E.Knuth娶牌、J.H.Morris和V.R.Pratt寒瓦，發(fā)表一個模式匹配算法于颖，可以大大避免重復遍歷的情況迟几，我們把它稱為KMP算法
一般匹配字符串時消请，我們從目標字符串str（假設長度為n）的第一個下標選取和ptr長度（長度為m）一樣的子字符串進行比較，如果一樣类腮，就返回開始處的下標值臊泰，不一樣，選取str下一個下標蚜枢，同樣選取長度為n的字符串進行比較缸逃，直到str的末尾（實際比較時，下標移動到n-m）厂抽。這樣的時間復雜度是O(n*m)需频。
KMP算法：可以實現復雜度為O(m+n)
算法代碼如下：
獲得子串的nextval數組:
void get_nextval (String T, int *nextval) {
?????? int i, j;
?????? i=1;
?????? j=0;
?????? nextval[1]=0;
?????? while (i<T[0]) {/*此處T[0]表示子串的長度*/
???????????? if(j == 0 || T[i] == T[j]) {/*T[i]表示后綴的單個字符,T[j]表示前綴的單個字符*/
?????????????????????? ++i;
?????????????????????? ++j;
?????????????????????? if(T[i] != T[j])/*若當前字符與前綴字符不同*/
???????????????????????????????? nextval[i] = j;/*則當前的j為nextval在i位置的值*/ ?????????????
??????????????????????? else
????????????????????????????????? nextval[i] = nextval[j]; /* 如果與前綴字符相同，則將前綴字符的nextval值賦值給nextval在i位置的值*/
????????????? }
????????????? else
?????????????????????? j = nextval[j];
?????????? }
}
獲得要匹配的子串在主串中的位置
/* 返回子串在主串中第pos個字符之后的位置筷凤。若不存在昭殉，則返回0*/
/*T非空苞七，1<=pos<=StrLength(S)。*/
int Index_KMP(String S, String T, int pos) {
??? int i = pos;/*i用于主串當前位置下標挪丢，若pos不為1蹂风，則從pos位置開始匹配*/
??? int j= 1;/*j用于子串T中當前位置下標值*/
??? int next[255];/*定義一next數組*/
??? get_nextval(T, next);/*對子串作分析，得到next數組*/
??? while( i <= S[0] && j <= T[0] )/*所i小于主串的長度且j小于子串的長度時乾蓬，循環(huán)繼續(xù)*/
??? {
???????? if (j==0 || S[i] == T[j])/*j=0或兩字母相等繼續(xù)*/
??????? {
??????????? ++i;
???????????? ++j;
????????? }
?????????? else{/*指針后退重新開始匹配*/
????????????????? j = next[j];/*j退回合適的位置惠啄，i值不變*/
???????????? }
??????? }
???????? if(j > T[0])
?????????????? return i-T[0];
????????? else
?????????????? return 0;
}
