快速模式匹配算法【KMP算法詳細(xì)介紹】

1. 模式匹配

模式匹配的模型大概是這樣的：給定兩個(gè)字符串變量S和P，其中S成為目標(biāo)串，其中包含n個(gè)字符，P稱為模式串，包含m個(gè)字符，其中m<=n。從S的給定位置(通常是S的第一個(gè)位置)開始搜索模式P。如果找到，則返回模式P在目標(biāo)串中的位置(即：P的第一個(gè)字符在S中的下標(biāo))。如果在目標(biāo)串S中沒有找到模式串P，則返回-1.這就是模式匹配的定義啦，下面來(lái)看看怎么實(shí)現(xiàn)模式匹配算法吧。

2. 樸素的模式匹配

樸素的模式匹配算法非常簡(jiǎn)單，容易理解，大概思路是這樣的：從S的第一個(gè)字符S0開始，將P中的字符依次和S中字符比較，若S0=P0 && …… && Sm-1 = Pm-1，則證明匹配成功，剩下的匹配無(wú)需進(jìn)行了，返回下標(biāo)0。若在某一步Si != Pi 則P中剩下的字符也不用比較了，不可能匹配成功了，然后從S中第二個(gè)字符開始與P中第一個(gè)字符進(jìn)行比較，同理，也是知道Sm = Pm-1或者找到某個(gè)i使得Si != S-1為止。依次類推若知道以S中第n-m個(gè)開始字符為止，還沒有匹配成功則證明S中不存模式P。(想想為什么這里強(qiáng)調(diào)是n-m)這個(gè)代碼實(shí)現(xiàn)應(yīng)該是非常簡(jiǎn)單的，具體開始參考strstr函數(shù)的內(nèi)部實(shí)現(xiàn)?？梢钥纯窗俣劝倏?，給個(gè)鏈接http://baike.baidu.com/view/745156.htm，這里不寫出來(lái)了，還得趕緊進(jìn)入正題KMP呢。

3. 快速模式匹配算法(KMP)

樸素的模式匹配效率不高的主要原因是進(jìn)行了重復(fù)的字符比較。下一次比較和上一次比較沒有任何的聯(lián)系，是樸素模式匹配的缺點(diǎn)，其實(shí)上一次比較的比較結(jié)果是可以利用的，這就產(chǎn)生了快速模式匹配。在樸素的模式匹配中，目標(biāo)串S的下標(biāo)移動(dòng)是一步一步的，這其實(shí)并不好，移動(dòng)步數(shù)沒有必要為1。

現(xiàn)在不妨假設(shè)，當(dāng)前匹配情況是這樣的：S0 …… St St+1 …… St+j 與 P0 P1…… Pj ，現(xiàn)在正在嘗試匹配的字符是St+j+1和Pj+1，并且St+j+1 != Pj+1，言外之意就是說(shuō)St St+1……St+j和P0 P1……Pj是完全匹配的。那么這個(gè)時(shí)候，S中下一次匹配開始位置應(yīng)該是什么呢??按照樸素的模式匹配，下次比較應(yīng)該從St+1開始，并且令St+1和P0比較，但是在快速模式匹配中并不是這樣，快速模式匹配選擇St+j+1和Pk+1比較，K是什么呢?K是這樣的一個(gè)值，使得P0 P1……Pk 和 Pj-k Pj-k+1……Pj完全匹配，不妨設(shè)k=next[j]，因此P0 P1……Pk和St+j-k St+j-k+1 ……St+j完全匹配。那么下一次要進(jìn)行匹配的兩個(gè)字符應(yīng)為St+j+1和Pk+1。S和P都沒有回溯到下標(biāo)0在進(jìn)行比較，這就是KMP之所以快的原因啦。

現(xiàn)在關(guān)鍵問(wèn)題來(lái)了，這個(gè)K怎么能得到呢?如果得到這個(gè)K值復(fù)雜度高，那這個(gè)思路就不好了，其實(shí)這個(gè)K呢，只和模式串P有關(guān)系，并且要求m個(gè)k，k = next[j]，因此只要算一次存儲(chǔ)到next數(shù)組中就可以了，并且時(shí)間復(fù)雜度和m有關(guān)系(線性關(guān)系)。看看具體怎么求next數(shù)組的值，即求k。

用歸納法求next[]：設(shè)next(0) = -1，若已知next(j) = k，欲求得next[j+1]。

(1)如果Pk+1 = Pj+1，顯然next[j+1] = k+1.如果Pk+1 != Pj+1，則next[j+1] < next[j]，于是尋找h < k 使得P0 P1……Ph = Pj-h Pj-h+1……Pj = Pk-h Pk-h+1……Pk。也就是說(shuō)h = next(k);看出來(lái)了吧，這是個(gè)迭代的過(guò)程。(也就是以前的結(jié)果對(duì)求以后的值有用)

(2)如果不存這樣的h，說(shuō)明P0 P1……Pj+1中沒有前后相等的子串，因此next[j+1] =-1.

(3)如果存在這樣的h，繼續(xù)檢驗(yàn)Ph和Pj是否相等。知道找到這中相等的情況，或者確定為-1求next[j+1]的過(guò)程結(jié)束。

KMP算法它的實(shí)現(xiàn)過(guò)程接近人為進(jìn)行模式匹配的過(guò)程。例如，對(duì)主串 A("ABCABCE")和模式串 B("ABCE")進(jìn)行模式匹配，如果人為去判斷，僅需匹配兩次。

圖 1 第一次人為模式匹配

第一次如圖 1 所示，最終匹配失敗。但在本次匹配過(guò)程中，我們可以獲得一些信息，模式串中 "ABC" 都和主串對(duì)應(yīng)的字符相同，但模式串中字符 'A' 與 'B' 和 'C' 不同。

因此進(jìn)行下次模式匹配時(shí)，沒有必要讓串 B 中的 'A' 與主串中的字符 'B' 和 'C' 一一匹配(它們絕不可能相同)，而是直接去匹配失敗位置處的字符 'A' ，如圖 2 所示：

圖 2 第二次人為模式匹配

至此，匹配成功。若使用 BF 算法，則此模式匹配過(guò)程需要進(jìn)行 4 次。

由此可以看出，每次匹配失敗后模式串移動(dòng)的距離不一定是 1，某些情況下一次可移動(dòng)多個(gè)位置，這就是 KMP 模式匹配算法。

那么，如何判斷匹配失敗后模式串向后移動(dòng)的距離呢?

模式串移動(dòng)距離的判斷

每次模式匹配失敗后，計(jì)算模式串向后移動(dòng)的距離是 KMP 算法中的核心部分。

其實(shí)，匹配失敗后模式串移動(dòng)的距離和主串沒有關(guān)系，只與模式串本身有關(guān)系。

例如，我們將前面的模式串 B 改為 "ABCAE"，則在第一次模式匹配失敗，由于匹配失敗位置模式串中字符 'E' 前面有兩個(gè)字符 'A'，因此，第二次模式匹配應(yīng)改為如圖 3 所示的位置：

圖 3 模式匹配過(guò)程示意圖

結(jié)合圖 1、圖 2 和圖 3 不難看出，模式串移動(dòng)的距離只和自身有關(guān)系，和主串無(wú)關(guān)。換句話說(shuō)，不論主串如何變換，只要給定模式串，則匹配失敗后移動(dòng)的距離就已經(jīng)確定了。

不僅如此，模式串中任何一個(gè)字符都可能導(dǎo)致匹配失敗，因此串中每個(gè)字符都應(yīng)該對(duì)應(yīng)一個(gè)數(shù)字，用來(lái)表示匹配失敗后模式串移動(dòng)的距離。

注意，這里要轉(zhuǎn)換一下思想，模式串向后移動(dòng)等價(jià)于指針 j 前移，如圖 4 中的 a) 和 b)。換句話說(shuō)，模式串后移相當(dāng)于對(duì)指針 j 重定位。

圖 4 模式串后移等價(jià)于 j 前移

因此，我們可以給每個(gè)模式串配備一個(gè)數(shù)組(例如 next[])，用于存儲(chǔ)模式串中每個(gè)字符對(duì)應(yīng)指針 j 重定向的位置(也就是存儲(chǔ)模式串的數(shù)組下標(biāo))，比如 j=3，則該字符匹配失敗后指針 j 指向模式串中第 3 個(gè)字符。

模式串中各字符對(duì)應(yīng) next 值的計(jì)算方式是，取該字符前面的字符串(不包含自己)，其前綴字符串和后綴字符串相同字符的最大個(gè)數(shù)再 +1 就是該字符對(duì)應(yīng)的 next 值。

前綴字符串指的是位于模式串起始位置的字符串，例如模式串 "ABCD"，則 "A"、"AB"、"ABC" 以及 "ABCD" 都屬于前綴字符串;后綴字符串指的是位于串結(jié)尾處的字符串，還拿模式串 "ABCD" 來(lái)說(shuō)，"D"、"CD"、"BCD" 和 "ABCD" 為后綴字符串。

注意，模式串中第一個(gè)字符對(duì)應(yīng)的值為 0，第二個(gè)字符對(duì)應(yīng) 1 ，這是固定不變的。因此，圖 3 的模式串 "ABCAE" 中，各字符對(duì)應(yīng)的 next 值如圖 5 所示：

圖 5 模式串對(duì)應(yīng)的 next 數(shù)組

從圖 5 中的數(shù)據(jù)可以看出，當(dāng)字符 'E' 匹配失敗時(shí)，指針 j 指向模式串?dāng)?shù)組中第 2 個(gè)字符，即 'B'，同之前講解的圖 3 不謀而合。

以上所講 next 數(shù)組的實(shí)現(xiàn)方式是為了讓大家對(duì)此數(shù)組的功能有一個(gè)初步的認(rèn)識(shí)。接下來(lái)學(xué)習(xí)如何用編程的思想實(shí)現(xiàn) next 數(shù)組。編程實(shí)現(xiàn) next 數(shù)組要解決的主要問(wèn)題依然是 "如何計(jì)算每個(gè)字符前面前綴字符串和后綴字符串相同的個(gè)數(shù)"。

仔細(xì)觀察圖 5，為什么字符 'C' 對(duì)應(yīng)的 next 值為 1?因?yàn)樽址?"AB" 前綴字符串和后綴字符串相等個(gè)數(shù)為 0，0 + 1 = 1。那么，為什么字符 'E' 的 next 值為 2?因?yàn)榫o挨著該字符之前的 'A' 與模式串開頭字符 'A' 相等，1 + 1 = 2。

如果圖 5 中模式串為 "ABCABE"，則對(duì)應(yīng) next 數(shù)組應(yīng)為 [0,1,1,1,2,3]，為什么字符 'E' 的 next 值是 3 ?因?yàn)榫o挨著該字符前面的 "AB" 與開頭的 "AB" 相等，2 + 1 =3。

因此，我們可以設(shè)計(jì)這樣一個(gè)算法，剛開始時(shí)令 j 指向模式串中第 1 個(gè)字符，i 指向第 2 個(gè)字符。接下來(lái)，對(duì)每個(gè)字符做如下操作：

如果 i 和 j 指向的字符相等，則 i 后面第一個(gè)字符的 next 值為 j+1，同時(shí) i 和 j 做自加 1 操作，為求下一個(gè)字符的 next 值做準(zhǔn)備，如圖 6 所示：

圖 6  i 和 j 指向字符相等

上圖中可以看到，字符 'a' 的 next 值為 j +1 = 2，同時(shí) i 和 j 都做了加 1 操作。當(dāng)計(jì)算字符 'C' 的 next 值時(shí)，還是判斷 i 和 j 指向的字符是否相等，顯然相等，因此令該字符串的 next 值為 j + 1 = 3，同時(shí) i 和 j 自加 1(此次 next 值的計(jì)算使用了上一次 j 的值)。如圖 7 所示：

圖 7  i 和 j 指向字符仍相等

如上圖所示，計(jì)算字符 'd' 的 next 時(shí)，i 和 j 指向的字符不相等，這表明最長(zhǎng)的前綴字符串 "aaa" 和后綴字符串 "aac" 不相等，接下來(lái)要判斷次長(zhǎng)的前綴字符串 "aa" 和后綴字符串 "ac" 是否相等，這一步的實(shí)現(xiàn)可以用 j = next[j] 來(lái)實(shí)現(xiàn)，如圖 8 所示：

圖 8  執(zhí)行 j=next[j] 操作

從上圖可以看到，i 和 j 指向的字符又不相同，因此繼續(xù)做 j = next[j] 的操作，如圖 9 所示：

圖 9 繼續(xù)執(zhí)行 j=next[j] 的操作

可以看到，j = 0 表明字符 'd' 前的前綴字符串和后綴字符串相同個(gè)數(shù)為 0，因此如果字符 'd' 導(dǎo)致了模式匹配失敗，則模式串移動(dòng)的距離只能是 1。

這里給出使用上述思想實(shí)現(xiàn) next 數(shù)組的 C 語(yǔ)言代碼：

void Next(char*T,int *next){
    next[1]=0;
    next[2]=1;
    int i=2;
    int j=1;
    while (i<strlen(T)) {
        if (j==0||T[i-1]==T[j-1]) {
            i++;
            j++;
            next[i]=j;
        }else{
            j=next[j];
        }
    }
}

代碼中 j=next[j] 的運(yùn)用可以這樣理解，每個(gè)字符對(duì)應(yīng)的next值都可以表示該字符前 "同后綴字符串相同的前綴字符串最后一個(gè)字符所在的位置"，因此在每次匹配失敗后，都可以輕松找到次長(zhǎng)前綴字符串的最后一個(gè)字符與該字符進(jìn)行比較。

Next函數(shù)的缺陷

圖 10  Next 函數(shù)的缺陷

例如，在圖 10a) 中，當(dāng)匹配失敗時(shí)，Next 函數(shù)會(huì)由圖 10b) 開始繼續(xù)進(jìn)行模式匹配，但是從圖中可以看到，這樣做是沒有必要的，純屬浪費(fèi)時(shí)間。

出現(xiàn)這種多余的操作，問(wèn)題在當(dāng) T[i-1]==T[j-1] 成立時(shí)，沒有繼續(xù)對(duì) i++ 和 j++ 后的 T[i-1] 和 T[j-1] 的值做判斷。改進(jìn)后的 Next 函數(shù)如下所示：

void Next(char*T,int *next){ 
    next[1]=0;
    next[2]=1;
    int i=2;
    int j=1;
    while (i<strlen(T)) {
        if (j==0||T[i-1]==T[j-1]) {
            i++;
            j++;
            if (T[i-1]!=T[j-1]) {
               next[i]=j;
            }
            else{
                next[i]=next[j];
            }
        }else{
            j=next[j];
        }
    }
}

使用精簡(jiǎn)過(guò)后的 next 數(shù)組在解決例如模式串為 "aaaaaaab" 這類的問(wèn)題上，會(huì)大大提高效率，如圖 11 所示，精簡(jiǎn)前為 next1，精簡(jiǎn)后為 next2：

圖 11  改進(jìn)后的 Next 函數(shù)

KMP 算法的實(shí)現(xiàn)

假設(shè)主串 A 為 "ababcabcacbab"，模式串 B 為 "abcac"，則 KMP 算法執(zhí)行過(guò)程為：

第一次匹配如圖 12 所示，匹配結(jié)果失敗，指針 j 移動(dòng)至 next[j] 的位置;

圖 12   第一次匹配示意圖

第二次匹配如圖 13 所示，匹配結(jié)果失敗，依舊執(zhí)行 j=next[j] 操作：

圖 13  第二次匹配示意圖

第三次匹配成功，如圖 14 所示：

圖 14  第三次匹配示意圖

很明顯，使用 KMP 算法只需匹配 3 次，而同樣的問(wèn)題使用 BF 算法則需匹配 6 次才能完成。

KMP 算法的完整 C 語(yǔ)言實(shí)現(xiàn)代碼為：

#include <stdio.h>
#include <string.h>
void Next(char*T,int *next){
    int i=1;
    next[1]=0;
    int j=0;
    while (i<strlen(T)) {
        if (j==0||T[i-1]==T[j-1]) {
            i++;
            j++;
            next[i]=j;
        }else{
            j=next[j];
        }
    }
}
int KMP(char * S,char * T){
    int next[10];
    Next(T,next);//根據(jù)模式串T,初始化next數(shù)組
    int i=1;
    int j=1;
    while (i<=strlen(S)&&j<=strlen(T)) {
        //j==0:代表模式串的第一個(gè)字符就和當(dāng)前測(cè)試的字符不相等；S[i-1]==T[j-1],如果對(duì)應(yīng)位置字符相等，兩種情況下，指向當(dāng)前測(cè)試的兩個(gè)指針下標(biāo)i和j都向后移
        if (j==0 || S[i-1]==T[j-1]) {
            i++;
            j++;
        }
        else{
            j=next[j];//如果測(cè)試的兩個(gè)字符不相等，i不動(dòng)，j變?yōu)楫?dāng)前測(cè)試字符串的next值
        }
    }
    if (j>strlen(T)) {//如果條件為真，說(shuō)明匹配成功
        return i-(int)strlen(T);
    }
    return -1;
}
int main() {
    int i=KMP("ababcabcacbab","abcac");
    printf("%d",i);
    return 0;
}

運(yùn)行結(jié)果為：

6