一.理論準(zhǔn)備
KMP算法為什么比傳統(tǒng)的字符串匹配算法快？KMP算法是通過(guò)分析模式串，預(yù)先計(jì)算每個(gè)位置發(fā)生不匹配的時(shí)候，可以省去重新匹配的的字符個(gè)數(shù)。整理出來(lái)發(fā)到一個(gè)next數(shù)組， 然后進(jìn)行比較，這樣可以避免字串的回溯，模式串中部分結(jié)果還可以復(fù)用，減少了循環(huán)次數(shù)，提高匹配效率。通俗的說(shuō)就是KMP算法主要利用模式串某些字符與模式串開(kāi)頭位置的字符一樣避免這些位置的重復(fù)比較的。例如 主串： abcabcabcabed ,模式串：abcabed。當(dāng)比較到模式串'e'字符時(shí)不同的時(shí)候完全沒(méi)有必要從模式串開(kāi)始位置開(kāi)始比較直接從模式串的'c'字符開(kāi)始比較就可以了。并且主串也不用回溯了。
傳統(tǒng)的匹配算法沒(méi)有利用匹配過(guò)的信息(模式串是知道的，那么部分匹配主串也是知道的)，每次都從頭開(kāi)始比較，速度很慢。
先介紹前綴數(shù)組(我自己這么叫的，不知道對(duì)不對(duì))是如何產(chǎn)生的。首先，要了解兩個(gè)概念："前綴"和"后綴"。 "前綴"指除了最后一個(gè)字符以外，一個(gè)字符串的全部頭部組合；"后綴"指除了第一個(gè)字符以外，一個(gè)字符串的全部尾部組合。
來(lái)看一個(gè)例子：chi表示模式串的前i個(gè)字符組成的前綴， next[i] = j表示chi中的開(kāi)始j個(gè)字符和末尾j個(gè)字符是一樣的(注意下標(biāo)是字符數(shù)目)，而且對(duì)于前綴chi來(lái)說(shuō)，這樣的j是最大值。next[i] = j的另外一個(gè)定義是：有一個(gè)含有j個(gè)字符的串，它既是chi的真前綴，又是chi的真后綴。
規(guī)定：next[1] = next[0] = 0，這個(gè)規(guī)定不像0！=1那樣，而是確實(shí)是這樣子，不懂得看上面的前后綴概念。注意：next數(shù)組里并不是首尾回文串，而是前綴等于后綴，理解這個(gè)對(duì)于遞推求next數(shù)組很重要喲。next[i]就是前綴數(shù)組，下面通過(guò)1個(gè)例子來(lái)看如何構(gòu)造前綴數(shù)組。
例：cacca有5個(gè)前綴，求出其對(duì)應(yīng)的next數(shù)組。前綴2為ca，顯然首尾沒(méi)有相同的字符，next[2] = 0，前綴3為cac，顯然首尾有共同的字符c，故next[3] = 1，前綴4為cacc，首尾有共同的字符c，故next[4] = 1，前綴5為cacca，首尾有共同的字符ca，故next[5] = 2。如果仔細(xì)觀察，可以發(fā)現(xiàn)構(gòu)造next[i]的時(shí)候，可以利用next[i-1]的結(jié)果。比如abcdabc，模式已求得next[7] = 3，為求next[8]，可以直接比較第4個(gè)字符和第8個(gè)字符，如果它們相等，則next[8] = next[7]+1 = 4，這是因?yàn)閚ext[7] = 3保證了前綴ch7的末尾4個(gè)字符的前3個(gè)字符是一樣的。但如果這兩個(gè)字符不想等呢？那就繼續(xù)迭代，利用(k=3)k = next[k]的值來(lái)求,直到k=0(next[8] = 0)或者字符相等(next[8] = k+1)。
二.算法實(shí)現(xiàn)
復(fù)制代碼代碼如下:
import java.util.ArrayList;
public class KMP {
//主串
static String str = "1kk23789456789hahha";
//模式串
static String ch = "789";
static int next[] = new int[20];
public static void main(String[] args) {
setNext();
ArrayList<Integer> arr = getKmp();
if(arr.size()!=0) {
for(int i=0; i<arr.size(); i++) {
System.out.println("匹配發(fā)生在:"+arr.get(i));
}
}else {
System.out.println("匹配不成功");
}
}
private static void setNext() {
// TODO Auto-generated method stub
int lenCh = ch.length();
next[0] = 0;
next[1] = 1;
//k表示next[i-1]的值
int k = 0;
for(int i=2; i<=lenCh; i++) {
k = next[k];
/*
* 這個(gè)while循環(huán)的作用找個(gè)例子看看就好理解了
* 我認(rèn)為是每次找最長(zhǎng)，一旦成功就停止，保證找到的是當(dāng)前最長(zhǎng)
*/
while(k!=0 && ch.charAt(i-1)!=ch.charAt(k)) {
k = next[k];
}
if(ch.charAt(i-1)==ch.charAt(k)) {
k++;
}//else就是k=0
//不是next[k] = k，i表示有幾個(gè)字符的前綴
next[i] = k;
}
}
private static ArrayList<Integer> getKmp() {
// TODO Auto-generated method stub
ArrayList<Integer> arr = new ArrayList<Integer>();
int lenStr = str.length();
int lenCh = ch.length();
//主串開(kāi)始的匹配位置
int pos = 0;
//模式串每次匹配位置
int k = 0;
//循環(huán)條件不是k<lenCh,這樣的話可能死循環(huán)(沒(méi)有匹配發(fā)生)
while(pos<lenStr) {
/*
* 首次進(jìn)入沒(méi)什么大作用，做要是為提高以后的匹配效率
* 寫(xiě)在最后一行也行
*/
k = next[k];
while(k<lenCh && str.charAt(pos)==ch.charAt(k)) {
pos++;
k++;
}
if(lenCh==k) {
arr.add(pos-k);
}else if(0==k) {
/*
* 不加這一句死循環(huán)
* 因?yàn)閚ext[0] = 0
* 比如abcd和abce，到de不匹配，此時(shí)執(zhí)行k = next[k](k=3),
* k變?yōu)?，發(fā)現(xiàn)d和a不匹配，此時(shí)k還是0，重復(fù)執(zhí)行以上步驟，那么死循環(huán)了
*/
pos++;
}//實(shí)際上else就是k = next[k]，所以才說(shuō)k = next[k]寫(xiě)在最后一行也行
}
return arr;
}
}
三.問(wèn)題擴(kuò)展
KMP算法的高效性往往是在模式串比較長(zhǎng)的時(shí)候才能體現(xiàn)出來(lái)(看next數(shù)組的推導(dǎo)過(guò)程)，而實(shí)際上模式串往往很短，回想自己使用辦公套件時(shí)查找的字符串長(zhǎng)度，所以實(shí)踐上大多使用BM算法來(lái)實(shí)現(xiàn)，感興趣的讀者可以自己查閱相關(guān)資料，或許可以再看看多模匹配(在主串中一次查找多個(gè)模式串)的AC自動(dòng)機(jī)、dictmatch算法。
