KMP匹配算法

Mar 10, 2013


最近看了一篇讲KMP算法的文章,看完之后总觉得少了点什么,对于KMP算法我还查找不过不少资料,发现对于KMP算法确实是有点难理解,虽然说对于求next[]数组的方法KMP算法的发明者已经给出了,但是对于尔等后生理解起来还是有一些困难的。本文针对那些对KMP匹配算法有些许了解的人,本文也都是自己在学习KMP算法的一些理解,其中有许不足恳请指正。

与KMP算法的相对是BF匹配算法。BF匹配算法的思想就是,当主串S与子串T进行匹配时,一旦S[i]与T[j]不相等时,那么S就要往回走,再比较S[n]与T[0]进行匹配,其中n < i.也就是说BF算法每次都是要进行回溯的,即使是匹配到了T的最后一个字符,一旦发现与S中的不相等,那么指向S的指针就要回溯,往回走继续下一轮与T[0]进行比较。有次知道,BF算法的时间复杂度是O(n*m)。

KMP的思想时,利用子串T中的自身某些性质(比如说开头的k个字符与某一个索引前的k个字符相等),当S[i]与T[j]不相等时,利用T的自身性质推导出T[j]与S[i]之前间接比较的字符,使得i不回溯继续往大于i的方向与T进行匹配。
首先看下例子 S:abcabcabdabba T:abcabd
第一次比较时:
alt text

第一次比较时,在所以为5的地方中断,不匹配。BF算法的下一次匹配就是在S[1]和T[0],那么利用KMP算法呢?下一次的匹配地方应该是S[3]和T[0]开始,如下:
alt text

蓝色的地方表示成功匹配,那么,KMP算法又是如何知道在第一次匹配不成功的时候第二次匹配就应该从S[3]和T[0]开始呢?观察子串T可知道
T[0] = T[3]
T[1] = T[4]
T[2] = S[5]
在S与T的比较过程中我们已经知道,S[3] = T[3],S[4] = T[4],下一步推导可知道:
S[3] = T[0]
S[4] = T[1]
T[0],T[1]是T开头的两个字符,也就是说,在T[5]之前,有两个连续字符与开头的两个连续字符相等。那么我们下一次只需要比较S[5]和T[2]。用KMP算法中的next数组值表示为:next[5] = 2.即表示,在子串T中,在索引5之前,有两个连续字符与开头的两个字符相等。

再来看一个例子: S:abcabcabdabba T:abaabd
第一次比较时:
alt text

在红色的地方比较不匹配,那么KMP算法中下一次的匹配地方在哪里呢? 观察T串发现:T[2] = T[0],由于S[0] = T[0],S[1] = T[1],S[2] != T[2],所以有S[0] = T[2],S[2] != T[0],根据KMP算法,我们下一次的比较地方应该是S[3]和T[0]比较。用KMP算法中的next数组值表示为:next[2] = -1,即表示:在T串中,索引为2前面的k-1个字符串和开头的k-1个字符不相等。

通过上面的例子我们可知,在保证S中的字符指针不回溯时就要利用T串本身的性质进行推导,算出下一次比较的索引,而推导出来的结果就用next数组表示,这样,我们的匹配就转到了求next数组上来了。好了,我们顺利的引出了next数组,由于算法已经给出next的定义,这里我贴出来下:
next[j]所表示的意义:

(1) next[0]= -1
意义:任何串的第一个字符的模式值规定为-1。

(2) next[j]= -1
意义:模式串T中下标为j的字符,如果与首字符相同,且j的前面的k-1个字符与开头的k-1个字符不等(或者相等但T[k]==T[j])(1≤k<j)。 如:T=”abCabCad” 则 next[6]=-1,因T[3]=T[6]

(3) next[j]=k
意义:模式串T中下标为j的字符,如果j的前面k个字符与开头的k个字符相等,且T[j] != T[k] (1≤k<j)。即T[0]T[1]T[2]…T[k-1]==T[j-k]T[j-k+1]T[j-k+2]…T[j-1],且T[j] != T[k].(1≤k<j);

(4) next[j]=0
意义:除(1)(2)(3)的其他情况。 再来看看next所表示的实际意义: next[]数组实际上表示的是在一个模式串中本身的性质:在一个模式串T中,以n为索引的字符与n之前的所有字符之间的关系表示法。 设在字符串S中查找模式串T,若S[m]!=T[n],那么,取T[n]的模式函数值next[n], 1.next[n]= -1 表示S[m]和T[0]间接比较过了,且不相等,下一次比较 S[m+1] 和T[0]

2.next[n]=0
表示比较过程中产生了不相等,下一次比较 S[m] 和T[0]。

3.next[n]= k (k>0 && k<n) 表示S[m]的前k个字符与T中的开始k个字符已经间接比较相等了,下一次比较S[m]和T[k]是否相等。

4.其他值,不可能。 知道next如何求之后,我们来求几个T串的next值。 1、T:abcac
next[0] = -1 由(1)可知
next[1] = 0 由(4)可知
next[2] = 0 1≤k<j,T[0] != T[1]
next[3] = -1 由(2)可知,T[3] = T[0],k=2,k-1=1,T[3]前的一个字符(c)与开头的一个字符不等(a)
next[4] = 1 由(3)可知,T[4] !=T[0],T[4] != T[1],T[3] = T[0]
2、T:abcccadbd
next[0] = -1 由(1)
next[1] = 0
next[2] = 0
next[3] = 0
next[4] = 0
next[5] = -1 由(2)
next[6] = 1 由(3)
next[7] = 0
next[8] = 0
3、T:ababcaabc
next[0] = -1
next[1] = 0
next[2] = -1
next[3] = 0 虽然T[0] = T[2],但T[1] = T[3],划为(4)
next[4] = 2
next[5] = -1
next[6] = 1
next[7] = 0 虽然T[6] = T[0],但T[7] = T[1]
next[8] = 2 T[6] = T[0],T[7] = T[1],T[8] != T[2]
既然知道了如何求next数组值,那么就写出next数组值的实现,KMP算法的发明人已经给出:

void getNextValue(const char *T, int next[])   
{   
    // 求模式串T的next函数值并存入数组 next。  
    int j = 0, k = -1;   
    next[0] = -1;   
    while ( T[j] != '\0' )   
    {   
        if (k == -1 || T[j] == T[k])   
        {   
            ++j;   
            ++k;   
            if (T[j]!=T[k])   
                next[j] = k;   
            else   
                next[j] = next[k];   
        }  
        else   
            k = next[k];   
    }  
}  

那么KMP算法:

int getPatternByKMP(const char* S,const char* T)   
{   
    if( !S || !T || T[0]=='\0' || S[0]=='\0' )  
        return -1;  
    int len=0;   
    const char * c = T;   
   
    int *next = new int[strlen(S)+1];  
    get_nextval(T,next);//求T的next函数值  
      
    int index = 0,i = 0,j = 0;   
    while(S[i]!='\0' && T[j]!='\0' )   
    {   
        if(S[i] == T[j])   
        {   
            ++i;    //继续比较后继字符  
            ++j;   
        }   
        else   
        {   
            index += j-next[j];   
            if(next[j] != -1)   
                j = next[j];    //模式串向右移动  
            else   
            {   
                j = 0;   
                ++i;   
            }   
        }   
    }  
    delete [] next;  
  
    if(T[j] == '\0')   
        return index; //匹配成功  
    else   
        return -1;         
}  

这里只给出了KMP算法的一种实现,还有一种实现就没有给出,鄙人觉得这就是比较好的实现了,一目了然。本文只是给出了对于KMP的实际理解,如果想了解其内部详细推导,网上已经有不少同仁给出来了,这里推荐一个比较详细的:http://blog.csdn.net/v_july_v/article/details/6545192,该文章对KMP的讲解比较详细。本文就只是给了大概,详细的还是看链接的文章比较好,这里顺便感谢一下链接的作者@v_JULY_v。