什么是KMP

KMP(D.E.Knuth,J.H.Morris,V.R.Prat)是三個發(fā)明者的名字首字母命名的。用于字符串匹配的經(jīng)典算法。

常規(guī)匹配算法

這個算法很抽象，研究了些時間才慢慢弄懂里面的一些奧秘之處，并借此記錄下來，以便后期回顧。

常規(guī)字符串匹配方式：

主串:ABC ABCDAB ABCDABCDABDE

模式串:ABCDABD

我們要在主串里查找匹配串是否存在，那么常規(guī)匹配方式如下：

主串和模式串都從頭開始匹配，當出現(xiàn)不匹配的字符時，如圖1所示，主串A字符和模式串的D字符不匹配，那么說明主串A開頭和模式串不匹配，主串往后移從B字符開始重新和模式串進行比較(如圖2)。因為主串B和模式串A不相等，所以主串往后移繼續(xù)和模式串比較(如圖3),重復以上操作，知道在主串中找到對應(yīng)的字串或者找不到。但是這樣比較的效率十分低，當出現(xiàn)不相等就會對模式串復位，然后從頭開始比較。要想比較速度加快，不用每次模式串都是從頭開始比較，下面介紹的KMP算法，就可以做到。

圖1

圖2

圖3

KMP實現(xiàn)

KMP的思想是當主串和模式串不相等時

1.主串不用像常規(guī)匹配那樣，需要從上一次的下一個位置開始重新和模式串進行匹配，保持當前位置不變和已經(jīng)移動過的模式串進行匹配,如果模式串移動的字符為0并且第一個字符和主串的當前字符也不相等，那么主串需要往后移動一個字符繼續(xù)和模式串匹配。

2.模式串將已經(jīng)對比過的好前綴一次性往后移動多個字符。

如圖4，當主串的空格和模式串的D不相等時，主串位置保持不變，模式串不用從0下標開始，而是從下標2開始重新匹配。因為ABCDAB主串和模式中進行對比后是相等的，那么，壞字符D的最長前綴和后綴集合是AB，長度為2。

模式串的起始位置依賴一張表叫部分匹配表。

圖4

部分匹配表：

圖5

部分匹配表是根據(jù)好前綴和好后綴共有元素的長度

A 前綴和后綴的集合為空 共有元素長度為0

AB 前綴【A】,后綴【B】 共有元素長度為0

ABC 前綴【A,AB】,后綴【BC, C】 共有元素長度為0

ABCD 前綴【A,AB,ABC】,后綴【BCD,CD,D】 共有元素長度為0

ABCDA 前綴【A,AB,ABC,ABCD】,后綴【BCDA,CDA,DA,A】 共有元素長度為1

ABCDAB 前綴【A,AB,ABC,ABCDA】,后綴【BCDAB,CDAB,DAB,AB,B】 共有元素長度為2

ABCDABD 前綴【A,AB,ABC,ABCDAB】,后綴【BCDABD,CDABD,DABD,ABD,BD,D】 共有元素長度為0

在程序中部分匹配表可以使用一個數(shù)組來保存，可以命名為next數(shù)組，next數(shù)組的下標為當前正在和主串進行比較的字符下標，其值是當前字符的好前綴和好后綴共有元素的長度。

我們約定next[0]為-1，那么上面的部分匹配轉(zhuǎn)換成next數(shù)組如下：

next[0]=-1 A A字符的好前綴和好后綴共有元素長度為0

next[1]=0 AB B字符的好前綴和好后綴共有元素長度為0

next[2]=0 ABC C字符的好前綴和好后綴共有元素長度為0

next[3]=0 ABCD D字符的好前綴和好后綴共有元素長度為0

next[4]=1 ABCDA A字符的好前綴和好后綴共有元素長度為1

next[5]=2 ABCDAB B字符的好前綴和好后綴共有元素長度為2

next[6]=0 ABCDABD D字符的好前綴和好后綴共有元素長度為0

代碼實現(xiàn)：

//s:模式串   len:模式串長度   next:next數(shù)組保存部分匹配表數(shù)據(jù)
void getNext(char *s, int len, int *next){
    int k = -1; //模式串s下標j的前后綴共有元素長度
    int j = 0;  //模式串的下標
    next[0] = -1;//第一個元素的共有元素約定為-1
    while(j < len){
        if(k == -1 || s[k] == s[j]){//k=-1表示是第一個字符
            //如果前綴和后綴有共有元素，那么前綴和后綴都后移一個字符，然后再次比較。
            k++;
            j++;
            next[j] = k; //將當前字符的前綴和后綴共有元素長度保存到next數(shù)組
        }else{
            k = next[k]; //如果不等，那么前綴字符串根據(jù)next數(shù)組往前查找和當前字符為后綴匹配的位置，
                               //如果一直找不到那么k值將會變成成0。就是說主串要從模式開頭進行匹配。
        }
    }
}

有了計算next數(shù)組的算法，那么KMP的實現(xiàn)就很簡單了

/*
*s:主串   slen:主串長度   p:模式串  plen:模式串長度   next:已經(jīng)計算過的next數(shù)組   res:匹配的下標位置
*
*/
int kmp(char*s , int slen, char*p, int plen, int *next, int *res){
    int s_index, p_index=0, res_index=0;
    for(s_index = 0; s_index < slen; s_index++){
            while(p_index > 0 && s[s_index] != p[p_index]){
                    //下一個匹配位為next數(shù)組的第j-1位
                    p_index = next[p_index-1]+1;
            }
            if(s[s_index] == p[p_index]){
                    p_index ++;//如果相等就都往后移一位
            }
            //如果匹配串的第一位一直和模式串第一位不相等，那么模式串id s_index一直往后移
            if(p_index == plen){
                    res[res_index++] = s_index-p_index+1;//應(yīng)為當模式串和匹配串相等時，匹配串的下標會加1，所以會多減1，后面要加上
                    p_index = 0;
            }
    }
    return res_index;
}

說明： 以上僅僅代表自己的想法。