KMP算法是字符串模式匹配當(dāng)中最經(jīng)典的算法苹享，原來大二學(xué)數(shù)據(jù)結(jié)構(gòu)的有講，但是當(dāng)時(shí)只是記住了原理弛矛，但不知道代碼實(shí)現(xiàn)够吩，今天終于是完成了KMP的代碼實(shí)現(xiàn)。
原理
KMP的原理其實(shí)很簡(jiǎn)單丈氓，給定一個(gè)字符串和一個(gè)模式串周循，然后找模式串在給定字符串中的位置。將兩個(gè)字符串轉(zhuǎn)換為字符數(shù)組万俗，然后從兩個(gè)數(shù)組的開始位置"i"湾笛，"j"開始匹配，如果相同闰歪，執(zhí)行"i++"嚎研，"j++"接著比較下一位；如果不相同库倘，就轉(zhuǎn)到模式串對(duì)應(yīng)next數(shù)組的對(duì)應(yīng)位置"next[j]"然后從該位置開始繼續(xù)與給定字符串的當(dāng)前位置"i"進(jìn)行比較临扮，換句話說就是將模式串提前了"j-next[j]"位繼續(xù)比較，不至于每次出現(xiàn)不匹配就又重新回到開始位置進(jìn)行匹配于樟，充分利用了已匹配過的位置公条。
代碼
KMP算法的關(guān)鍵是得到模式串的next數(shù)組：
public static int[] next(char[] p) { int len = p.length; int[] next = new int[len]; next[0] = 0; next[1] = 0; //首先給next[0]和next[1]賦值拇囊，這兩個(gè)數(shù)字是固定的 for(int i = 2; i < len; i++) { int k = next[i - 1]; //用一個(gè)整型數(shù)字進(jìn)行遍歷 while(k >= 0) { if(p[i - 1] == p[k]) { next[i] = k + 1; //當(dāng)匹配到字符時(shí)就能得到當(dāng)前位置的next值迂曲，然后結(jié)束循環(huán) break; } k--; } } return next; }
得到next數(shù)組之后就可以進(jìn)行KMP匹配：
public int kmpSearch(char[] s, char[] p) { int i = 0, j = 0; //從0開始 int slen = s.length, plen = p.length; int[] next = next(p); while(i < slen && j < plen) { if(s[i] == p[j]) { //挨個(gè)進(jìn)行匹配 i++; j++; } else { j = next[j]; //如果不相等，返回next[j]位置繼續(xù)向后匹配寥袭，不用和前面的進(jìn)行比較 } } if(j == plen) //如果匹配到最后路捧，說明匹配成功，返回匹配成功的開始位置 return i - j; return -1; //否則就是匹配失敗传黄，返回-1 }
KMP算法還有一個(gè)進(jìn)階的next算法杰扫，求nextval數(shù)組：
public int[] nextVal(char[] p) { int len = p.length; int[] nextval = new int[len]; nextval[0] = -1; int i=-1, j = 0; while(j < len - 1) { if(i == -1 || p[j] == p[i]) { ++i; ++j; if(p[j] != p[i]) nextval[j] = i; else nextval[j] = nextval[i]; }else i = nextval[i]; } return nextval; }
