KMP算法詳解

字符串模式匹配我們相信大家都有遇過，然而我們也習慣用簡單匹配法（即Brute-Force算法)，其基本思路就是一個個逐一對比下去，這也是我們大家熟知的方法，然而這種算法的效率并不高，但利于理解。

假設主串s="ababcabcacbab",模式串為t="abcac"，我們用肉眼很容易看出匹配位置為是s[5]--s[10];利用簡單匹配算法代碼如下：

int BF(string s,string t)//Brute-Force,簡單匹配算法
{
    int origin=-1;//模式匹配的起始位置
    for(int i=0;i<s.size();i++)
    {
        int k;
        for(k=0;k<t.size();k++)
        {
            if(s[i+k]!=t[k])
               break;
        }
        if(k==t.size())//匹配成功
        {
            origin=i;
            break;
        }
    }
    return origin;//返回匹配成功的位置，若為-1，則匹配失敗
}

然后這種算法效率顯而易見效率并不高，其中包含了過多的不必要操作，并不能很好地達到實際工作中需要的效率。這種算法在最好的情況下時間復雜度為O(m),在最壞的情況下時間復雜度為M(nm)。

KMP算法

KMP算法較Brute-Force算法有較大的改進，主要消除了主串指針的回溯，從而是算法的效率有了某種程度的提高。

為了消除主串的指針回溯，需要分析模式串t，我們利用next[]數組來記錄存放這些“部分匹配信息”。

next[]計算規則如下：

1）next[j]=-1; j=0;

2) next[j]=max(k); 0<k<j,p[0....k-1]=p[j-k...j-1];

3) next[j]=0; 其他條件

例如：計算ababa的next[]數組值

按照上面的規則我們可以填寫出下表的next[]數組

根據上面規則，當j=0，next[j]=-1,所以第一個a的next值為-1；

當j=1時，0<k<j這樣的k不存在，所以屬于其他條件，即為0；

當j=4時，0<k<j,這樣的k=1,2,3,因為要求最大的K,即從大到小驗證k是否滿足p[0....k-1]=p[j-k...j-1]，若一個都不滿足，屬于其他條件，即為0，

當k=3時,str1=p[0....k-1]=aba,str2=p[j-k...j-1]=bab,str1!=str2,所以k!=3;

當k=2時,str1=p[0....k-1]=ab,str2=p[j-k...j-1]=ab,str1==str2,滿足條件,所以k=2;

根據上面的條件，可以輕易寫出next的計算函數;

//計算next數組，t為計算字符串
void calculateNext(int  & next,string t)
{
    for(int j=0;j<t.size();j++)
    {
        bool state=true;//是否是等于0的情況
        if(j==0)
            next=-1;
        else 
        {
            int k=j-1;//0<k<j,獲取最大的k
            while(k>0)
            {
                string str1="",str2="";
                for(int i=0;i<=k-1;i++)
                {
                    str1=str1+t[i];
                    str2=str2+t[j-k+i];
                }
                if(str1==str2)//若，p[0....k-1]=p[j-k...j-1];
                {

                    *(next+j)=k;
                    state=false;//不是等于0的情況
                    break;
                }
                k--;


        }
        if(state)<strong>//滿足其他條件，即為0</strong> *(next+j)=0;
    }

}

}</pre> 

    


    計算出匹配信息next后，我們就可以進行KMP匹配了，


    主要思路是：

假設i和j分別為指示主串和模式串中正在比較的字符的當前位置，并對i 和j 賦初值0。
在匹配的過程中，若si=tj，則i和j分別增加1，繼續進行比較。
否則，若j=0，si!=tj,則從s的下一個字符開始，即i增加一,若j！=0，令j=next[j]
 

    


    理解了上面的思路，就很容易編寫出KMP匹配代碼：

//kmp匹配算法,s為主串，t為模式串
int KMP(int * next,string s,string t)
{
    int j=0,i=0;//i為主串s正在匹配的字符，j為t正在匹配的字符


while(i<s.size()&&j<t.size())
{
    if(t[j] == s[i])
    {
        j++;i++;
    }
    else
    {
        if(j==0) 
        {
            i++;//若第一個字符就匹配失敗，則從s的下一個字符開始
        }
        else
        {

            j = *(next+j);//,也可以j=next[j],用next確定t應回溯到的字符
        }
    }
}
if(j < t.size())//整個過程匹配失敗
{
    return -1;
}
return i-t.size();//匹配成功
//第二種寫法
/*2. while(i < s.size())  
     {  
              while(j > -1 && t[j] != s[i])  
                      j = next[j];  
              i++, j++;  
              if(j >= t.size()) return i - j;  
     }  
 return -1;  */




}</pre> 

    


    至此，我們就完成了KMP算法的學習。在學習KMP過程中，我發了一篇“另一種”有關的KMP算法，更好理解學習，附上鏈接：http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html 


    


    本次KMP的源代碼地址：https://github.com/longpo/algorithm 


來自：http://hm4123660.iteye.com/blog/2194569