查找子字元串----KMP算法深入剖析

 假設主串：a b a b c a b c a c b a b

      子串：a b c a c

1、一般比對算法

逐個字元的比較，比對過程如下：

　　第一趟比對

　　a b a b c a b c a c b a b

　　a b c

　　第二趟

　    a

　　第三趟

　　    a b c a c

　　第四趟

　　      a

　　第五趟

　          a

　　第六趟

　　          a b c a c

比對成功。

性能分析：情況好：時間複雜度O(m+n)；情況差：時間複雜度O(m*n)。　　

2、一般比對算法改進

　　即KMP算法。可以發現上面的算法，每一趟比對過程中出現字元不等時，回溯指針，如果将其改進，指針不回溯，利用已經得到的部分比對的結果将模式向右移動的更遠一些，然後繼續比較。那麼算法性能會得到大大的提高。

　　看到上面的過程，在第三趟的比對過程中，當i=6,j=4字元不等時，又從i=3,j=0重新開始比較。其實可以容易發現,在i=3和 j=0，i=4和i=0以及i=5和j=0這3次比較都是不必進行的。因為從第三趟部分比對結果就可以得出，主串中第3,4,5個字元是’b’,’c’,’a’。而模式中第一個字元是’a’，是以無需和這3個字元進行比較了，緊需要向右移動3個字元繼續進行i=6,j=1時字元串比較就行了。那麼一種理想的模式比對就可以的出來了。

KMP比對過程如下：

　　第一趟

　　          a b c a c 

比對成功，可以看出算法效率提高了不少。

3、剖析KMP算法：

假設(n>m)

　　主串：s0 s1 s2 s3 s4 s5 s6 …… s(n)

　　模式：p0 p1 p2 p3 p4……….p(m)      

當比對過程中産生失配（s(i)!=p(j)）時，主串的第i個字元應與模式中的哪個字元相比較？假設此時與模式中的第k（k<j）個字元相比較，那麼就有p0p1…p(k-1)=s(i-k)s(i-k+1)…s(i-1) --式1(就好像上面中綠的的字元a,這裡是從模式中第1個字元開始比較與主串中字元a相同)。

　　當比對失配時（s(i)!=p(j)）,可以得到p0p1p2p3…p(j-1)=s(i-j)s(i-j+1)…s(i-1) --式2

　　從式2可以得到p(j-k)p(j-k+1)…p(j-1)=s(i-k)s(i-k+1)..s(i-1) --式3

　　由式1和式3可以得到p0p1…p(k-1)=p(j-k)p(j-k+1)…p(j-1) --式4

　　若令next[j]=k，則next[j]表明當模式中第j個字元與主串中相應字元失配時，在模式中需要重新和主串中該字元進行比較的字元位置。那麼next 函數定義為：

                     （1）-1 當j=0時

　　next[j]= （2）max{k|0<k<j 且式4成立}

                     （3）0  其他情況

那麼此時next值如何求得呢？

     由定義知道next[0]=-1;設next[j]=k，這表明在模式串中有這樣關系p0p1…p(k-1)=p(j-k)p(j-k+1)…p(j-1) （0<k<j） --式5。此時next[j+1]的值有兩中情況：

   （1）若p(k)=p(j), 則：p0p1…p(k)=p(j-k)p(j-k+1)…p(j) --式6，即next[j+1]=k+1。

   （2）若p(k)!=p(j),則：p0p1…p(k)!=p(j-k)p(j-k+1)…p(j)--式7，此時可以把該問題看成模式比對的問題，整個模式串既是主串又是模式串，這裡應将模式向右移動next[k](模式中第k個字元與主串失配時，需要移動的位置)位置，和主串中的第j個字元相比較。若next[k]=k’,且p(j)=p(k’),則可以得到next[j+1]=next[k]+1即 next[j+1]=next[next[j]]+1。那麼還要注意下當模式中上一個字元串與下一個字元串相等時候，它們next值是相等的。

4、KMP算法代碼：

[html] view plaincopy

#include "stdafx.h"  

#include "iostream.h"  

#include "string.h"  

//next數組  

void GetNext(char *subStr,int *next)  

{  

    int len=strlen(subStr);  

    next[0]=-1;  

    int i=0,j=-1;  

    while(i<len)  

    {         

        if(j==-1||subStr[i]==subStr[j])  

        {  

            i++;  

            j++;  

            //前字尾字元相等  

            if(subStr[i]==subStr[j])  

                next[i]=next[j];  

            else  

                next[i]=j;  

        }  

        else  

            j=next[j];  

    }  

}  

//KMP算法  

int KMP(char *str,char *subStr)  

    int lenStr=strlen(str);  

    int lenSubstr=strlen(subStr);  

    int i=0,j=0;  

    int *next=new int[lenStr];  

    GetNext(subStr,next);  

    //周遊主串和子串  

    while(i<lenStr&&j<lenSubstr)  

    {  

        //與一般比對算法增加了j==-1判斷  

        if(j==-1||str[i]==subStr[j])   

        //j回溯，i不變  

            j=next[j];   

    delete[] next;  

    //傳回子串的位置  

    if(j>=lenSubstr)  

        return i-lenSubstr;  

    else  

        return -1;  

int main()  

    char *str="iloveyouoooyouloveme";  

    char *subStr1="youoooyou";  

    char *subStr2="youoooyou2";  

    cout<<KMP(str,subStr1)<<endl;  

    cout<<KMP(str,subStr2)<<endl;  

    return 0;  

}