模式匹配的KMP算法詳解

這種由D.E.Knuth,J.H.Morris和V.R.Pratt同時(shí)發(fā)現(xiàn)的改進(jìn)的模式匹配算法簡(jiǎn)稱(chēng)為KMP算法。大概學(xué)過(guò)信息學(xué)的都知道，是個(gè)比較難理解的算法，今天特把它搞個(gè)徹徹底底明明白白。

注意到這是一個(gè)改進(jìn)的算法，所以有必要把原來(lái)的模式匹配算法拿出來(lái)，其實(shí)理解的關(guān)鍵就在這里，一般的匹配算法：

int Index(String S,String T,int pos)//參考《數(shù)據(jù)結(jié)構(gòu)》中的程序
{
i=pos;j=1;//這里的串的第1個(gè)元素下標(biāo)是1
while(i<=S.Length && j<=T.Length)
{
if(S[i]==T[j]){++i;++j;}
else{i=i-j+2;j=1;}//**************(1)
}
if(j>T.Length) return i-T.Length;//匹配成功
else return 0;
}

匹配的過(guò)程非常清晰，關(guān)鍵是當(dāng)‘失配’的時(shí)候程序是如何處理的？回溯，沒(méi)錯(cuò)，注意到(1)句，為什么要回溯，看下面的例子：

S:aaaaabababcaaa T:ababc

aaaaabababcaaa
ababc.(.表示前一個(gè)已經(jīng)失配)
回溯的結(jié)果就是
aaaaabababcaaa
a.(babc)
如果不回溯就是
aaaaabababcaaa
aba.bc
這樣就漏了一個(gè)可能匹配成功的情況
aaaaabababcaaa
ababc

為什么會(huì)發(fā)生這樣的情況？這是由T串本身的性質(zhì)決定的，是因?yàn)門(mén)串本身有前后'部分匹配'的性質(zhì)。如果T為abcdef這樣的，大沒(méi)有回溯的必要。

改進(jìn)的地方也就是這里，我們從T串本身出發(fā)，事先就找準(zhǔn)了T自身前后部分匹配的位置，那就可以改進(jìn)算法。

如果不用回溯，那T串下一個(gè)位置從哪里開(kāi)始呢？

還是上面那個(gè)例子，T為ababc，如果c失配，那就可以往前移到aba最后一個(gè)a的位置，像這樣：
...ababd...
ababc
->ababc

這樣i不用回溯，j跳到前2個(gè)位置，繼續(xù)匹配的過(guò)程，這就是KMP算法所在。這個(gè)當(dāng)T[j]失配后，j應(yīng)該往前跳的值就是j的next值，它是由T串本身固有決定的，與S串無(wú)關(guān)。

《數(shù)據(jù)結(jié)構(gòu)》上給了next值的定義：
0 如果j=1
next[j]={Max{k|1<k<j且'p1...pk-1'='pj-k+1...pj-1'
1 其它情況

我當(dāng)初看到這個(gè)頭就暈了，其實(shí)它就是描述的我前面表述的情況，關(guān)于next[1]=0是規(guī)定的，這樣規(guī)定可以使程序簡(jiǎn)單一些，如果非要定為其它的值只要不和后面的值沖突也是可以的；而那個(gè)Max是什么意思，舉個(gè)例子：

T:aaab

...aaaab...
aaab
->aaab
->aaab
->aaab

像這樣的T，前面自身部分匹配的部分不止兩個(gè)，那應(yīng)該往前跳到第幾個(gè)呢？最近的一個(gè)，也就是說(shuō)盡可能的向右滑移最短的長(zhǎng)度。

OK，了解到這里，就看清了KMP的大部分內(nèi)容，然后關(guān)鍵的問(wèn)題是如何求next值？先不管它，先看如何用它來(lái)進(jìn)行匹配操作，也就是說(shuō)先假設(shè)已經(jīng)有了next值。

將最前面的程序改寫(xiě)成：

int Index_KMP(String S,String T,int pos)
{
i=pos;j=1;//這里的串的第1個(gè)元素下標(biāo)是1
while(i<=S.Length && j<=T.Length)
{
if(j==0 || S[i]==T[j]){++i;++j;} //注意到這里的j==0,和++j的作用就知道為什么規(guī)定next[1]=0的好處了
else j=next[j];//i不變（不回溯）,j跳動(dòng)
}
if(j>T.Length) return i-T.Length;//匹配成功
else return 0;
}

OK,是不是非常簡(jiǎn)單？還有更簡(jiǎn)單的，求next值，這也是整個(gè)算法成功的關(guān)鍵，從next值的定義來(lái)求太恐怖了，怎么求？前面說(shuō)過(guò)了，next值表達(dá)的就是T串的自身部分匹配的性質(zhì)，那么，我只要將T串和T串自身來(lái)一次匹配就可以求出來(lái)了，這里的匹配過(guò)程不是從頭一個(gè)一個(gè)匹配，而是從T[1]和T[2]開(kāi)始匹配，給出算法如下：

void get_next(String T,int &next[])
{
i=1;j=0;next[1]=0;
while(i<=T.Length)
{
if(j==0 || T[i]==T[j]){++i;++j; next[i]=j;/**********(2)*/}
else j=next[j];
}
}

看這個(gè)函數(shù)是不是非常像KMP匹配的函數(shù)，沒(méi)錯(cuò)，它就是這么干的！注意到(2)語(yǔ)句邏輯覆蓋的時(shí)候是T[i]==T[j]以及i前面的、j前面的都匹配的情況下，于是先自增，然后記下來(lái)next[i]=j，這樣每當(dāng)i有自增就會(huì)求得一個(gè)next[i]，而j一定會(huì)小于等于i，于是對(duì)于已經(jīng)求出來(lái)的next，可以繼續(xù)求后面的next，而next[1]=0是已知，所以整個(gè)就這樣遞推的求出來(lái)了，方法非常巧妙。

這樣的改進(jìn)已經(jīng)是很不錯(cuò)了，但算法還可以改進(jìn)，注意到下面的匹配情況：

...aaac...
aaaa.
T串中的'a'和S串中的'c'失配，而'a'的next值指的還是'a'，那同樣的比較還是會(huì)失配，而這樣的比較是多余的，如果我事先知道，當(dāng)T[i]==T[j]，那next[i]就設(shè)為next[j]，在求next值的時(shí)候就已經(jīng)比較了，這樣就可以去掉這樣的多余的比較。于是稍加改進(jìn)得到：

void get_nextval(String T,int &next[])
{
i=1;j=0;next[1]=0;
while(i<=T.Length)
{
if(j==0 || T[i]==T[j])
{ ++i;++j;
if(T[i]!=T[j]) next[i]=j;
else next[i]=next[j];//消去多余的可能的比較,next再向前跳
}
else j=next[j];
}
}

匹配算法不變。

到此就完全弄清楚了，以前老覺(jué)得KMP算法好神秘，真不是人想出來(lái)的，其實(shí)不然，它只不過(guò)是對(duì)原有的算法進(jìn)行了改進(jìn)。可見(jiàn)基礎(chǔ)的經(jīng)典的東西還是很重要，你有本事‘廢’了經(jīng)典，就創(chuàng)造了進(jìn)步。