数据结构 第8讲 KMP算法

数据结构第8讲 KMP算法

讲这个算法之前，我们首先了解几个概念：

串：又称字符串，是由零个或多个字符组成的有限序列。如S="abcdef" 子串：串中任意个连续的字符组成的子序列，称为该串的子串，原串称为子串的主串。如T="cde"，T是S的子串。子串在主串中的位置，用子串的第一个字符在主串中出现的位置表示。T在S中的位置为3。

模式匹配：子串的定位运算称为串的模式匹配或串匹配。 假设有两个串S，T，设S为主串，也称正文串，T为子串，也称为模式，在主串S中查找与模式T相匹配的子串，如果查找成功，返回匹配的子串第一个字符在主串中的位置。 最笨的办法就是穷举所有S的所有子串，判断是否与T匹配。 例如：S="abaabaabeca"，T=" abaabe"，求子串T在主串S中的位置。

1. 从S串第1个字符开始：i=1，j=1，比较两个字符是否相等，如果相等，则i++，j++；如果不等则执行第2步；

1. 从S串第2个字符开始：即i退回到i-j+2的位置，即i=2，j=1，比较两个字符是否相等，如果相等，则i++，j++；如果不等则执行第3步；

1. 从S串第3个字符开始：即i退回到i-j+2的位置，即i=3，j=1，比较两个字符是否相等，如果相等，则i++，j++；如果不等则执行第4步；

1. 从S串第4个字符开始：即i退回到i-j+2的位置，即i=4，j=1，比较两个字符是否相等，如果相等，则i++，j++；此时T串比较完了，执行第5步；

1. 需要返回子串在主串S中第一个字符出现的位置，即i-m=10-6=4，m为T串的长度。

上述算法称为BF(Brute Force)算法，Brute Force的意思是蛮力，暴力穷举。其时间复杂度最坏达到O(n*m)，n，m分别为S、T串的长度。 实际上，完全没必要从S的每一个字符开始，暴力穷举每一种情况，Knuth、Morris和Pratt对该算法进行了改进，称为KMP算法。 我们再回头看刚才的例子： 从S串第1个字符开始：i=1，j=1，比较两个字符是否相等，如果相等，则i++，j++；按照BP算法，如果不等则i退回到i-j+2的位置，即i=2，j=1。

其实i不用回退，让j回退到第3个位置，接着比较即可。

是不是像T串向右滑动了一段距离？ 为什么可以这样？为什么让j回退到第3个位置？而不是第2个？第四个？ 因为T串中开头的两个字符和i指向的字符前面的两个字符一模一样噢，那j就可以回退到第3个位置继续比较了，因为前面两个字符已经相等了。

那我们怎么知道T串中开头的两个字符和i指向的字符前面的两个字符一模一样？难道还要比较？我们发现i指向的字符前面的两个字符和T串中j指向的字符前面两个字符一模一样，因为它们一直相等，才会i++，j++走到后面的位置。

也就是说，我们不必判断T串中开头的两个字母和i指向的字符前面的两个字符是否一样，只需要在T串本身比较就可以了。即T′的前缀和T′的后缀比较即可：

判断T′="abaab"的前缀和后缀是否相等，找相等前缀后缀的最大长度。 长度为1的：前缀"a"，后缀："b"，不等× 长度为2的：前缀"ab"，后缀："ab"，相等√ 长度为3的：前缀"aba"，后缀：" aab"，不等× 长度为4的：前缀"abaa"，后缀："baab"，不等× 注意：前缀和后缀不可以取字符串本身。串的长度为5，前缀和后缀长度最多达到4。 相等前缀后缀的最大长度为l=2，则j就可以回退到第l+1=3个位置继续比较了。 现在我们可以写出通用公式，next[j]表示j可以回退的位置，T′="t1t2…tj-1"，则：

那么我们很容易求出T="abaabe"的next[]数组：

      解释：

     j=1：根据公式next[1]=0；      j=2：T′="a"，没有前缀和后缀，next[2]=1；      j=3：T′="ab"，前缀为"a"，后缀为"b"，不等，next[3]=1；      j=4：T′="aba"，前缀为"a"，后缀为"a"，相等且l=1；前缀为"ab"，后缀为"ba"，不等，next[4]=l+1=2；

j=5：T′="abaa"，前缀为"a"，后缀为"a"，相等且l=1；前缀为"ab"，后缀为"aa"，不等；前缀为"aba"，后缀为"baa"，不等，因此next[5]=l+1=2；

j=6：T′="abaab"，前缀为"a"，后缀为"b"，不等；前缀为"ab"，后缀为"ab"，相等且l=2；前缀为"aba"，后缀为"aab"，不等；前缀为"abaa"，后缀为"baab"，不等，取最大长度2，因此next[6]=l+1=3。

这样找所有的前缀和后缀比较，是不是也是暴力穷举？

那怎么办呢？Look……

用动态规划递推一下：

首先大胆假设，我们已经知道了next[j]=k，即：

那么next[j+1]=?

考察以下两种情况：

1. tk=tj：那么next[j+1]=k+1，即相等前缀和后缀的长度比next[j]多1。

1. tk≠tj：当两者不相等时，我们又开始了这两个串的模式匹配，找next[k]的位置tk′与tj比较，程序中的处理，只需要把next[k]赋值给k，即k←next[k]，然后再比较tk与tj是否相等，如果相等则next[j+1]=k+1；

如果不相等，则继续向前找next[k′]，如果不相等，继续向前找，直到找到next[1]=0，停止，此时next[j+1]=0+1=1，即从第一个字符开始。

求解next[]的代码实现如下：

void get_next(SString T, int next[]) //求模式串T的next函数值
{ 
    int j=1, k= 0;
    next[1] = 0;
    while (j<T[0])   // T[0]为模式串T的长度
        if (k== 0 || T[j] ==T[k])
            next[++j]=++k;
        else
            k= next[k];
}

用上述方法再次求解求出T="abaabe"的next[]数组：

解释：

              1.  初始化时next[1]=0，j=1，k=0，进入循环，判断满足k==0，则执行next[++j]=++k，即next[2]=1，此时j=2，k=1；

              2.   进入循环，判断满足T[j]==T[k]，T[2]≠T[1]，则执行k=next[k]，即k=next[1]=0，此时j=2，k=0；

      3. 进入循环，判断满足k==0，则执行next[++j]=++k，即next[3]=1，此时j=3，k=1；

      4. 进入循环，判断满足T[j]==T[k]，T[3]=T[1]，则执行next[++j]=++k，即next[4]=2，此时j=4，k=2；

      5. 进入循环，判断满足T[j]==T[k]，T[4]≠T[2]，则执行k=next[k]，即k=next[2]=1，此时j=4，k=1；

      6. 进入循环，判断满足T[j]==T[k]，T[4]=T[1]，则执行next[++j]=++k，即next[5]=2，此时j=5，k=2；

      7. 进入循环，判断满足T[j]==T[k]，T[5]=T[2]，则执行next[++j]=++k，即next[6]=3，此时j=6，k=3；

      8. j=T[0]，循环结束。

结果是不是和穷举前缀后缀一模一样？ 有了next[]数组，就很容易进行模式匹配了，当S[i]≠T[j]时，j退回到next[j]的位置继续比较即可。 这样求解非常方便，迅速，但是也发现有一个问题：当S[i]≠T[j]时，j退回到next[j]，然后S[i]与T[k]比较。这样的确没错，但是如果T[k]=T[j]，这次比较就没必要了，因为我们刚知道S[i]≠T[j]啊，那么肯定S[i]≠T[k]，完全没必要再比了。

再向前找下一个next[]，即找next[k]的位置，继续比较就可以了。本来应该和第k个位置比较呢，相当于跳到了k的下一个位置。减少了一次无效比较。

修改程序：

求解next[]的改进代码实现如下：
        void get_next2(SString T, int next[]) //求模式串T的next函数值
       { 
            int j=1, k= 0;
            next[1] = 0;
          while (j<T[0])   // T[0]模式串T的长度
         {
              if(k==0||T[j]==T[k])
              {
                   j++;
                   k++;
                   if(T[j]==T[k])
                       next[j]=next[k]; //调到k的下一个位置，即next[k]
                  else
                      next[j]=k;
              }
              else
                     k=next[k];
         }

完美～～～

/***KMP及改进算法***/
#include<cstring>
#include<iostream>
using namespace std;
#define Maxsize 100
typedef char SString[Maxsize+1];        //0号单元存放串的长度
bool StrAssign(SString &T, char *chars)//生成一个其值等于chars的串T
{
    int i;
    if (strlen(chars)>Maxsize)
        return false;
    else
{
        T[0]=strlen(chars);
        for(i=1; i<=T[0]; i++)
{
T[i]=*(chars+i-1);
cout<<T[i]<<" ";
}
cout<<endl;
        return true;
    }
}
void get_next(SString T, int next[])//计算next函数值
{
    int j=1,k=0;
    next[1]=0;
    while(j<T[0])
    {
     if(k==0||T[j]==T[k])
           next[++j]=++k;
        else
            k=next[k];
    }
   cout<<"-----next[]-------"<<endl;
   for(j=1;j<=T[0];j++)
        cout<<next[j]<<" ";
   cout<<endl;
}
void get_next2(SString T, int next[])//计算next函数值改进算法
{
    int j=1,k=0;
    next[1]=0;
    while(j<T[0])
    {
         if(k==0||T[j]==T[k])
        {
             j++;
            k++;
           if(T[j]==T[k])
               next[j]=next[k];
           else
               next[j]=k;
         }
        else
            k=next[k];
    }
     cout<<"-----next[]-------"<<endl;
     for(j=1;j<=T[0];j++)
           cout<<next[j]<<" ";
     cout<<endl;
}
int Index_KMP(SString S, SString T, int pos, int next[])//KMP算法
{     //  利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法
    //其中，T非空，1≤pos≤StrLength(S)
    int i=pos, j=1,sum=0;
    while (i<=S[0] && j<=T[0])
    {
       sum++;
      if (j==0||S[i]==T[j])  //继续比较后面的字符
        {
            i++;
            j++;
        }
        else
            j=next[j]; //模式串向右移动
    }
    cout<<"一共比较了"<<sum<<"次"<<endl;
    if (j>T[0]) //匹配成功
        return i-T[0];
    else
        return 0;
}
int main()
{
    SString S,T;
   cout<<"串S："<<"  ";
    StrAssign(S,"aabaaabaaaabea");
   cout<<"串T："<<"  ";
    StrAssign(T,"aaaab");
    int *p=new int[T[0]+1]; //生成T的next数组
    cout<<endl;
    cout<<"KMP算法运行结果："<<endl;
    get_next(T,p);
    cout<<"主串和子串在第"<<Index_KMP(S,T,1,p)<<"个字符处首次匹配\n";
    cout<<endl;
    cout<<"改进的KMP算法运行结果："<<endl;
   get_next2(T,p);
    cout<<"主串和子串在第"<<Index_KMP(S,T,1,p)<<"个字符处首次匹配\n";
    return 0;
}