数据结构第8讲 KMP算法

一时失言乱红尘 2022-05-17 10:49 176阅读 0赞

数据结构第8讲 KMP算法

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

串：又称字符串，是由零个或多个字符组成的有限序列。如S=”abcdef”

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

![这里写图片描述][70]

模式匹配：子串的定位运算称为串的模式匹配或串匹配。

假设有两个串S，T，设S为主串，也称正文串，T为子串，也称为模式，在主串S中查找与模式T相匹配的子串，如果查找成功，返回匹配的子串第一个字符在主串中的位置。

最笨的办法就是穷举所有S的所有子串，判断是否与T匹配。

例如：S=”abaabaabeca”，T=” abaabe”，求子串T在主串S中的位置。

从S串第1个字符开始：i=1，j=1，比较两个字符是否相等，如果相等，则i++，j++；如果不等则执行第2步；  
![这里写图片描述][70 1]

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

![这里写图片描述][70 2]  
从S串第3个字符开始：即i退回到i-j+2的位置，即i=3，j=1，比较两个字符是否相等，如果相等，则i++，j++；如果不等则执行第4步；  
![这里写图片描述][70 3]

从S串第4个字符开始：即i退回到i-j+2的位置，即i=4，j=1，比较两个字符是否相等，如果相等，则i++，j++；此时T串比较完了，执行第5步；  
![这里写图片描述][70 4]

需要返回子串在主串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。

![这里写图片描述][70 5]

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

![这里写图片描述][70 6]

是不是像T串向右滑动了一段距离？

为什么可以这样？为什么让j回退到第3个位置？而不是第2个？第四个？

因为T串中开头的两个字符和i指向的字符前面的两个字符一模一样噢，那j就可以回退到第3个位置继续比较了，因为前面两个字符已经相等了。

![这里写图片描述][70 7]

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

![这里写图片描述][70 8]

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

![这里写图片描述][70 9]

判断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”，则：

![这里写图片描述][70 10]

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

![这里写图片描述][70 11]

解释：
    
     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，即：

![这里写图片描述][70 12]

那么next\[j+1\]=?

考察以下两种情况：

tk=tj：那么next\[j+1\]=k+1，即相等前缀和后缀的长度比next\[j\]多1。  
![这里写图片描述][70 13]

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

如果不相等，则继续向前找next\[k′\]，如果不相等，继续向前找，直到找到next\[1\]=0，停止，此时next\[j+1\]=0+1=1，即从第一个字符开始。  
![这里写图片描述][70 15]

求解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\[\]数组：

![这里写图片描述][70 16]

解释：

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\]，完全没必要再比了。

![这里写图片描述][70 17]

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

![这里写图片描述][70 18]  
修改程序：

求解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 #

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<

[70]: /images/20220517/925cd25327ea48d59db48248ef025d5c.png
[70 1]: /images/20220517/99a8eba066a344ca92ca6181c862e594.png
[70 2]: /images/20220517/067195e8eb504efb974274c148bd4770.png
[70 3]: /images/20220517/823218ff947a41cf9b43b3fef58803ac.png
[70 4]: /images/20220517/545ec32ebdf540fc9d1b0fe108676755.png
[70 5]: /images/20220517/a5473a2a6dfb4398a29678157e54c3c0.png
[70 6]: /images/20220517/ca09d726a5214d539812c3a7a63935a9.png
[70 7]: /images/20220517/2777b6751b9c408bbe72673dd90570b8.png
[70 8]: /images/20220517/c074386a89624f21afeee553a30a3a3e.png
[70 9]: /images/20220517/cb0b95849b834085a28203fe9e10fb7f.png
[70 10]: /images/20220517/bc385a214a6e4920827ec9d7a2622c5f.png
[70 11]: /images/20220517/0998e35bf9f942469210cf0a4bcf70cd.png
[70 12]: /images/20220517/1f7407edc19049f1909ce2b5747e39b2.png
[70 13]: /images/20220517/178ac56d11c04e4f8e846edebaf68f2c.png
[70 14]: /images/20220517/ad432313ee964e5d9f383cb62eaf6352.png
[70 15]: /images/20220517/02a9c46957d9401c8ecca46c321c5a09.png
[70 16]: /images/20220517/0500f8730ebb4bafb08b56a7d94e22ad.png
[70 17]: /images/20220517/c8945cd8073040519b48bf827130e005.png
[70 18]: /images/20220517/ab60cb655212431593d84395dee0b275.png