KMP算法详解

 

KMP算法：

       是在一个“主文本字符串” S 内查找一个“词” W 的出现，通过观察发现，在不匹配发生的时候这个词自身包含足够的信息来确定下一个匹配将在哪里开始，以此避免对以前匹配过的字符重新检查。

 

常规的比较方法：                                                            KMP方法：

被查找串：a b c a b c a b d a b b                                     被查找串：a b c a b c a b d a b b    

   模式串：a b c a b d                                                          模式串：a b c a b d 

                   ||                                                                                          ||

(下一次匹配)  ||                                                                      (下一次匹配)  ||

 

被查找串：a b c a b c a b d a b b                                      被查找串：a b c a b c a b d a b b

   模式串：   a b c a b d                                                        模式串：        a b c a b d

 

 

KMP字符串模式匹配通俗点就是在一个字符串中定位另一个串的高效算法。简单匹配算法事件的复杂度为O(m*n)，KMP匹配算法的时间复杂度为O(m+n)。

 

对于上例(字符串从0计数)，在模式串中T[5]=d,主串中S[5]=c：发生不匹配。而next[5]=2.所以下一次就是比较S[5]和T[2]。所以KMP的关键是求串的模式函数值next[n]。

 

共有两种方法来定义next函数值，并且对应这两种next值有两种方式的移动模式串的方式，但是产生的效果是相同的。

第一种方法：

定义：

        (1).next[0]=-1.

        (2).next[j]=-1: 模式串T中下标为j的字符如果与首字符相同，且j前面的1---k个字符与1--k个字符不等

                               (或者相等但是T[k]=T[j])(1=<k<j) 如：T="abcabcad",next[6]=-1.

        (3).next[j]=k:  模式串中下标为j的字符，j前面的k的字符与开头的k的字符相等，并且T[j]!=T[k]。

                               (有点感觉像最长的字符串前缀=字符串后缀的)(1=<k<j)

        (4).next[j]=0: 除了(1)(2)(3)的三种情况。

举例：

 

下标	0	1	2	3	4
T	a	b	c	a	c
next	-1	0	0	-1	1

 

下标	0	1	2	3	4	5	6	7	8
T	a	b	a	b	c	a	a	b	c
next	-1	0	-1	0	2	-1	1	0	2

另解图表：

              2：说明前面有个长度为2的对称子串

              0：说明前面有一个长度为1的对称子串，但是T[j]=t[1]

             -1：说明前面没有对称子串

             此处的对称是指最两端的对称块

代码：

    void get_nextval(const char* T,int 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];//A

             }

           else

                k=next[k];

     }

程序分析：k=-1说明将要从头开始进行匹配。k记录着已经匹配成功的字符的个数，其实就是从开头开始已经匹配到第几个字符了。当第一次进行匹配时，进入if条件句。++k表示第一个字符，++i表示要匹配的第一个字符。如果不相等，将此刻k的值赋值给nexti。如果相等，就要看nextk的值，并把nextk的值赋给nexti。其实就是看nextk里面有没有对称的字符。

 

 

下标	0	1	2	3	4	5	6	7	8
T	a	t	a	m	a	t	a	m	t
next	-1	0	-1	1	-1	-1	-1	1	4

k是记录到目前为止已经有几个匹配成功的字符。

j是记录当前的字符

next[j]是记录当前字符的模式函数值

next[k]是记录已经匹配成功的字符里面有没有对称的子串。例如next[3]说明已经匹配成功的ata里面有1个对称子串。

               当j=7时可以看到k=3.而此时T[7]=T[3].故按照规矩2,next[7]=-1.但是我们看到此时，next[k]也就是

               next[3]=1说明有一个对称子串在里面，就是T[2]=T[0].而此时根据对称关系k=3的这个字符的前一个字符

               (T[2])是与j=7的前一个字符相等的，也就是能得到T[0]是与j=7的前一个字符相等的。并且T[7]与T[2]也间接

                比较了，因为T[7]=T[k],而nextk=1，也就是说T[k]!=T[1]的，所以T[7]!=T[1].所以在这个条件下我们就

               得到next[7]=next[3]=1.

               又例如j=6时，可以看到k=2，而此时T[6]=T[2].按照规矩2，next[6]=-1.并且此时next[k]也就是next[2]=

               -1.所以next[6]=next[2]=-1.

              又例如next[3]=1,此时j=3，k=1；T[3]!=T[1].k=next[k]=next[1]=0.说明没有子串，否则就会从有子串

               的k开始进行下次匹配，也就是第k+1个字符开始匹配。当j=8时，k=4；next[8]=4.因为T[8!]=T[4],所以将

               k=next[k]=next[4]=-1.说明没有子串，我们需要从头开始匹配。如果next[4]=1.即说明T[3]=T[0],又有

               T[7]=T[3].我们得到T[7]=T[0].然后我们将比较T[1]和T[9]就可以了。但是此时next[4]=-1，我们需要比较

               T[0]和T[9].

使用next[j]:

             在字符串S中查找模式串T，若S[m]!=T[n],那么：

            (1).next[n]=-1表示S[m]和T[0]已经间接比较过了(我们可以看到所有为-1的nextj都是与第一个字符相同，

                                          如果S[m]!=T[n],则S[m]!=T[0]),下一次比较S[m+1]和T[0].

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

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

                                                     T[k].S[m]和T[n]不相等，说明m前面的字符和n前面的字符是相等的，由于

                                                      next[n]=k,说明n前面的k个字符和最前面的k个字符是相等的。所以m前面的k个

                                                      字符等于n最前面的k个字符。字符是从0开始计数的，所以此时我们比较S[m]

                                                      和T[k]就可以了。

完整代码使用：

 

 

void get_nextval(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];

       }

}

int KMP(const char *Text,const char* Pattern) 

{

       if( !Text||!Pattern|| Pattern[0]=='/0' || Text[0]=='/0' )//

              return -1;//空指针或空串，返回-1。

       int len=0;

       const char * c=Pattern;

       while(*c++!='/0')//移动指针比移动下标快。

       {    

              ++len;//字符串长度。

       }

       int *next=new int[len+1];

       get_nextval(Pattern,next);//求Pattern的next函数值

   

       int index=0,i=0,j=0;

       while(Text[i]!='/0' && Pattern[j]!='/0' )

       {

              if(Text[i]== Pattern[j])

              {

                     ++i;// 继续比较后继字符

                     ++j;

              }

              else

              {

                     index += j-next[j];

                     if(next[j]!=-1)

                            j=next[j];// 模式串向右移动

                     else

                     {

                            j=0;

                            ++i;

                     }

              }

       }

   

       delete []next;

       if(Pattern[j]=='/0')

              return index;// 匹配成功

       else

              return -1;      

}

int main()//abCabCad

{

       char* text="bababCabCadcaabcaababcbaaaabaaacababcaabc";

       char*pattern="adCadCad";

       //getNext(pattern,n);

       //get_nextval(pattern,n);

       cout<<KMP(text,pattern)<<endl;

       return 0;

}

 

其他资源：http://blog.csdn.net/oneil_sally/article/details/3440784

               http://blog.csdn.net/sparkliang/article/details/5284579

               http://www.zhiwenweb.cn/Category/Security/1267.htm

 

方法二就是数组前缀法：其实本质上是相同的就是next函数的求法不同以及使用起来也不同

 

位置i	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
子串	a	g	c	t	a	g	c	a	g	c	t	a	g	c	t	g
前缀next	0	0	0	0	1	2	3	1	2	3	4	5	6	7	4	0

 

  表格解释：包含当前字符的字符串的前缀和后缀的最长对称子串。这里的对称是指块对称就是：abcab，前后两个ab是

                 对称的，我们思路就是得出前缀next的值，也就是对称的大小以及如何使用next值来进行kmp优化。

  还有一个难点就是在13 字符和14 字符的前缀变化是如何得来的。说白了就是第一种方法中的子串的原因。

 

 

规则：

(1).当前面字符的前一个字符的对称程度为0的时候，只要将当前字符与子串第一个字符进行比较。

(2).如果前面一个字符的next值是1，那么我们就把当前字符与子串第二个字符进行比较，因为前面的是1，说明前面的字        符已经和第一个相等了，如果这个又与第二个相等了，说明对称程度就是2了。

(3).按照上面的推理，如果一直相等，就一直累加.如果遇到下一个不相等了，那么说明不能继承前面的对称性了，这种情况       只能说明没有那么多对称了，但是不能说明一点对称性都没有，所以遇到这种情况就要重新来考虑，这个也是难点所         在。

      不相等后的情况分析:

                                    位置i=0到14如下,我加的括号只是用来说明问题：

                                    (a g c t a g c )( a g c t a g c) t

            我们可以看到这段，最后这个t之前的对称程度分别是：1，2，3，4，5，6，7,倒数第二个c往前看有7个字符对         称，所以对称为7。但是到最后这个t就没有继承前面的对称程度next值，所以这个t的对称性就要重新来求。

      这里首要要申明几个事实:

             1、t 如果要存在对称性，那么对称程度肯定比前面这个c 的对称程度小，所以要找个更小的对称，这个不用解释                     了吧，如果大那么t就继承前面的对称性了。

     2、要找更小的对称，必然在对称内部还存在子对称，而且这个t必须紧接着在子对称之后。

 

如下图说明:

 

 

 

 

 

 

 

 

 

 

从上面的理论我们就能得到下面的前缀next数组的求解算法:

 

void SetPrefix(const char *Pattern, int prefix[])

{

     int len=CharLen(Pattern);//模式字符串长度。

     prefix[0]=0;

     for(int i=1; i<len; i++)

     {

         int k=prefix[i-1];

         //不断递归判断是否存在子对称，k=0说明不再有子对称，Pattern[i] != Pattern[k]说明虽然           对称，但是对称后面的值和当前的字符值不相等，所以继续递推

         while( Pattern[i] != Pattern[k]  &&  k!=0 )               

             k=prefix[k-1];    

         //继续递归,其实就是看前面有没有更小的对称

         if( Pattern[i] == Pattern[k])

        //找到了这个子对称，或者是直接继承了前面的对称性，这两种都在前面的基础上++

              prefix[i]=k+1;

         else

              prefix[i]=0;      

        //如果遍历了所有子对称都无效，说明这个新字符不具有对称性，清0

     }

}

 

 

 

 

k表示已经存在的对称子串的长度。如k=p[13]=7，说明在进行字符14的处理时前面已经有2个长度为7的对称子串，开始比对P[14]和P[7],由于从0开始计数，P[7]就代表字符串的第八个字符。此时不相等，我们令k=p[6].

p[6]是第7个字符，与p[14]的前一个字符是相等的，因为有对称关系，并且p[0...6]=p[7....13]。现在我们看p[6]的值就是想看钱7个字符有没有对称的子串。我们发现p[6]=3,所以p[012]=p[456]=p[789]=p[11,12,13]

此时，k=p[6]=3，说明存在紧贴着字符14的子对称，也说明这个子对称的长度为3。有p[012]=p[11,12,13]。说明再进行对称匹配时，最开始的3个字符和字符14之前的3个字符已经相等，此时我们只需要比较字符14和第四个字符也就是字符3即可。

如果字符串变成：agctagcd agctagcd t  最后一个t没找到对称，则下一次匹配由于没有对称子串，将会从头开始

 

得到next后的使用也就是完整代码：

 

int KMP(const char *Text,const char* Pattern) 

{

       if( !Text||!Pattern|| Pattern[0]=='/0' || Text[0]=='/0' )//

              return -1;//空指针或空串，返回-1。

       int len=0;

       const char * c=Pattern;

       while(*c++!='/0')//移动指针比移动下标快。

       {    

              ++len;//字符串长度。

       }

       int *next=new int[len+1];

       SetPrefix(Pattern,next);//求Pattern的next函数值

   

       int j=0;

           for(int i=0;i<n;)

           {

               while(j>0&&(B[j]!=A[i]))

                        j=p[j-1];//第i个字符前j个字符与最开始的前j个字符相等。故i和第j+1个字符开始比较,也就是字

                                        符j，因为计数是从零开始

               if(A[j]==B[i])

                        j+=1;

               if(j==len-1)

                   对齐,对齐点是字符i-len，也就是第i-m+1个字符;

           }   

       delete []next;

       if(Pattern[j]=='/0')

              return index;// 匹配成功

       else

              return -1;      

}

资源：http://blog.csdn.net/yearn520/article/details/6729426

         http://www.matrix67.com/blog/archives/115/

在理解了第一种方法之后，我们发现第二种方法的实质是与第一种相同的但是第二种方法感觉上要直观很多，好理解很多。