KMP算法中next函数的理解

时间:2022-03-18 20:03:33

    首先要感谢http://blog.csdn.net/v_july_v/article/details/7041827以及http://blog.chinaunix.net/uid-27164517-id-3280128.html两篇博文的作者,参考这两篇博文才对KMP算法有了初步认识,本文的一些内容也是来自于这两篇之中。KMP算法与BF算法的优略、回溯不回溯这些问题本文不作说明,而主要说明next函数(通常保存为一个next数组)的意义。这正是KMP算法难于理解的地方。

  为了方便起见,在不会起歧义的情况下做如下约定:下标都从0开始; 假设字符串为S,那么Si 表示第i个字符或者只有第i个字符的字符串;SiSi+1Si+2表示子串,如S1S2S3,S4S5等等;pre(S,i)表示字符串S的位置i之前的字符串,即S0S1...Si-1;next函数和next数组表示同一个意思。本文分为两节,第一节讲next函数的意义,得出需要满足的两个条件;第二节是具体代码以及相关说明。

第一节  next函数的意义

    我们知道,KMP的基本匹配过程如下:在字符串T中查找模式P,需要记录T中的当前位置以及P中的当前位置 j。当Ti=Pj的时候i和j都自增;当Ti!=Pj时,令j=next(j),然后继续匹配。这样就跳过了一些字符,而这些字符,本质上来讲与字符串P0P1...Pj-1的前缀和后缀能匹配的最大长度相关。以图一作解释,来倒推next(j)的意义:

KMP算法中next函数的理解

图 1

    在T中查找P,P0P1P2P3P4=T1T2T3T4T5,但P5!=T6(i=6,j=5)。此时令j=next(j)。假设next[5]=2, 则跳过三个字符,新的j=2,从这个位置开始比较。能跳过的条件是什么?其一,从虚线部分可知必须保证P0P1=P3P4;其二,P5不能等于P2,因为之前我们知道了P5!=T6,如果P5=P2,那么P2肯定不等于T6。再次强调观察虚线部分,发现P0P1和P3P4正好是字符P5前面的字符串(即P0P1P2P3P4)的前缀和后缀。

    图1中,P5!=T6时跳过了三个字符,next[5]=2。再看图2:next(5)分别等于4,3,1,0的情况。

KMP算法中next函数的理解

图 2

    仔细观察图2中的四种情况,均需要符合上面所说的条件。对于图2的最后一幅图,此种情况的条件是P0P1P2P3P4没有相等的前缀和后缀,且P0!=P5。那么如果后一个条件不满足呢,那么显然P应该再移一个位置,对应的情况如图3:

KMP算法中next函数的理解

图 3

    图3中,next(5)=-1。因此next=-1的情况:Pj=P0,且P0P1...Pj-1没有任何相等的前缀和后缀。另外,一般地,如果P0就发生失配,那么显然i也要加一,因此next(0)=-1。

    在此作一小结,k=next(j)需要满足的两个条件如下:

    条件1. k是P0P1...Pj-1最长匹配的前缀和后缀的长度.

    条件2. Pj!=Pk.

第二节  next函数的求法

    利用以上知识,我们就知道求next函数的思路了。基本思路是利用上面的第一个条件(寻找最长匹配的前后缀),而第二个条件(Pj!=Pnext(j))则作为优化。这样一步步理解会对算法思路更清晰一点。

基本思路: 利用条件1

使用归纳法:假设next(j)=k,则P0P1...Pk-1=Pj-k...Pj-2Pj-1,那么next(j+1)有两种情况:

1. 如果Pk=Pj,则P0P1...Pk=Pj-k...Pj-1Pj,所以next(j+1)=k+1=next(j)+1。

2. 如果Pk!=Pj,这是可以看做另外一个字符串匹配的问题,主串和模式串都是p,当匹配失败时,k=next(k)。

因此得到如下算法:

void get_nextval(char const* ptrn, int plen, int* nextval)    
{    
    int i = 0;
    nextval[i] = -1;    
    int j = -1;    
    while( i < plen-1 )    
    {    
        if( j == -1 || ptrn[i] == ptrn[j] )   //对应情况1
        {    
            ++i;    
            ++j;    
            next(i)=j;
        }    
        else                                  //对应情况2
            j = nextval[j];    
    }    
}   

    上述算法中,ptrn是模式串,plen是模式串长度,nextval数组保存所有位置的next值。该算法不考虑条件2,因此有可能发生Pi=Pnext(i)这种情况。在缺少该条件的情况下也可以用于做字符串匹配。假设next(i)=k,当匹配到i失效时,i=next(i)=k,这时候肯定也失效,因此又寻找k对应的next值,这样算法得以进行。

优化:利用条件2

比较常见的算法对情况1做了优化,如下:

 1 void get_nextval(char const* ptrn, int plen, int* nextval)    
 2 {    
 3     int i = 0;
 4     nextval[i] = -1;    
 5     int j = -1;    
 6     while( i < plen-1 )    
 7     {    
 8         if( j == -1 || ptrn[i] == ptrn[j] )   //对应情况1
 9         {    
10             ++i;    
11             ++j;    
12             if( ptrn[i] != ptrn[j] )
13                 nextval[i] = j;
14             else    
15                 nextval[i] = nextval[j];    
16         }    
17         else                                  //对应情况2
18             j = nextval[j];    
19     }    
20 }

  该版本的算法考虑了条件2,因此进入情况1的时候,next(i)!=j。我们可以考虑一条查询链,如图4:

KMP算法中next函数的理解

    图4

    假设现在刚刚运行完13行,得出next[i]=j。此时必然有ptrn[i]!=ptrn[j]。因此下个循环的时候会跳转到18行。该next链一直往前搜寻,直到某个位置k,ptrn[k]与ptrn[i]相等。该k就是最新的j值,这样回到情况1,接着按照条件1优化。另外,当j==-1也应当进入情况1,因为不能往前搜寻了。

    以上就是next数组的求解过程,往后就可以利用next数组进行字符串查找了。在写查找算法的过程中,可以发现与求next数组的算法过程惊人的一致。这也是KMP算法的一个特点,把两者结合起来,更能够理解它的奥妙所在。