【数据结构与算法】字符串匹配 KMP 算法

今天药忘吃喽~ 2022-12-01 01:24 207阅读 0赞

1.  单模式串匹配  
    BF 算法和 RK 算法  
    BM 算法和 **KMP 算法**
2.  多模式串匹配算法  
    Trie 树和 AC 自动机

### KMP 算法 ###

KMP 算法是根据三位作者（D.E.Knuth，J.H.Morris 和 V.R.Pratt）的名字来命名的，算法的全称是 Knuth Morris Pratt 算法，简称为 KMP 算法。

### 思想 ###

1，KMP算法的核心思想，与BM算法非常相近。假设主册是a，模式串是b。再模式串与主串匹配的过程中，当遇到不可匹配的字符的时候，找到一些规律，将模式串往后多滑动几位，跳过肯定不会匹配的情况。  
2，当遇到坏字符的时候，我们就要把模式串往后滑动，在滑动的过程中，只要模式串和好前缀有上下重合，前面几个字符的比较，就相当于拿好前缀的后缀子串，跟模式串的前缀子串在比较。  
3，KMP算法就是试图寻找一种规律：在模式串和主串匹配的过程中，当遇到坏字符后，对于已经对过的好前缀，将模式串一次性滑动很多位？  
4，我们只需要拿好前缀本身，在它的后缀子串中，查找最长的那个可以跟好前缀的前缀子串匹配的。假设最长的可匹配的那部分前缀子串是\{v\}，长度是k。我们把模式串一次性往后滑动j-k位，相当于，每次遇到坏字符的时候，我们就把j更新为k，i不变，然后继续比较。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]

5，KMP算法也可以提前构建一个数组，用来存储模式串中每个前缀（这些前缀都有可能是好前缀）的最长可匹配子串的结尾字符下标。将这个数组定义为**next数组**，很多书中将这个数组起名为\*\*失效函数（failure function）。\*\*next数组的下标是每个前缀结尾字符下标，数组的值是这个前缀的最长可以匹配的前缀子串的结尾字符下标。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 1]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 2]

### next数组（失效函数）计算方法 ###

**精髓：k = next\[k\]  
因为前一个的最长串的下一个字符不与最后一个相等，需要找前一个的次长串，问题就变成了求0到next(k)的最长串，如果下个字符与最后一个不等，继续求次长串，也就是下一个next(k)，直到找到，或者完全没有**  
①：按照下标从小到大，依次计算next数组的值。当我们要计算next\[i\]时，前面的next\[0\]，next\[1\]，……，next\[i-1\]应该已经计算出来了。利用已经计算出来的next值，可以快速推导出next\[i\]的值。  
②：如果next\[i-1\] = k-1，即子串b\[0,k-1\]是b\[0,i-1\]的最长可匹配前缀子串。如果子串b\[0,k-1\]的下一个字符b\[k\]，与b\[0,i-1\]的下一个字符b\[i\]匹配，那子串b\[0,k\]就是b\[0,i\]的最长可匹配前缀子串。所以，next\[i\]等于k。但是，如果b\[0,k-1\]的下一个字符b\[k\]跟b\[0,i-1\]的下一个字符不相等，则需要进一步处理。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 3]

③：假设b\[0,i\]的最长可匹配后缀子串是b\[r，i\]。如果把最后一个字符去掉，那b\[r,i-1\]肯定是b\[0,i-1\]的可匹配后缀子串，但不一定是最长可匹配后缀子串。所以，既然b\[0,i-1\]最长可匹配后缀子串对应的模式串的前缀子串的下一个字符并不等于b\[i\]，那么我们就可以考察b\[0，i-1\]的次长可匹配后缀子串b\[x,i-1\]对应的可匹配前缀子串b\[0，i-1-x\]的下一个字符b\[i-x\]是否等于b\[i\]。如果等于，那\[x，i\]就是b\[0，i\]的最长可匹配后缀子串。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 4]

④：求b\[0，i-1\]的次长可匹配后缀子串，次长可匹配后缀子串肯定被包含在最长可匹配后缀子串中，而最长可匹配后缀子串又对应最长可匹配前缀子串b\[0,y\]。于是，查找b\[0，i-1\]的次长可匹配后缀子串，这个问题就变成，查找b\[0,y\]的最长匹配后缀子串的问题。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 5]

⑤：按照这个思路，可以考察完所有的b\[0,i-1\]的可匹配后缀子串b\[y,i-1\]，直到找到一个可匹配的后缀子串，他对应的前缀子串的下一个字符等于b\[i\]，那这个b\[y，i\]就是b\[0,i\]的最长可匹配后缀子串。

// a, b分别是主串和模式串；n, m分别是主串和模式串的长度。
    public static int kmp(char[] a, int n, char[] b, int m) { 
      int[] next = getNexts(b, m);
      int j = 0;
      for (int i = 0; i < n; ++i) { 
        while (j > 0 && a[i] != b[j]) {  // 一直找到a[i]和b[j]
          j = next[j - 1] + 1;
        }
        if (a[i] == b[j]) { 
          ++j;
        }
        if (j == m) {  // 找到匹配模式串的了
          return i - m + 1;
        }
      }
      return -1;
    }
    
    
    // b表示模式串，m表示模式串的长度
    private static int[] getNexts(char[] b, int m) { 
      int[] next = new int[m];
      next[0] = -1;
      int k = -1;
      for (int i = 1; i < m; ++i) { 
      //因为前一个的最长串的下一个字符不与最后一个相等，需要找前一个的次长串，问题就变成了求0到next(k)的最长串，如果下个字符与最后一个不等，继续求次长串，也就是下一个next(k)，直到找到，或者完全没有
        while (k != -1 && b[k + 1] != b[i]) { 
          k = next[k];
        }
        if (b[k + 1] == b[i]) { 
          ++k;
        }
        next[i] = k;
      }
      return next;
    }

### KMP算法复杂度分析 ###

KMP算法包含两部分，\*\*第一部分是构建next数组，第二部分是借助next数组匹配。\*\*所以时间复杂度分析要分别从这两部分来分析。

**关于第一部分的时间复杂度：**  
计算next数组得代码中，第一层for循环中i从1到m-1，即内部的代码被执行了m-1次，for循环内部代码有一个while循环，如果我们能知道每次for循环，while循环平均执行的次数，假设是k，那时间复杂度就是O(k\*m)。但是，while循环执行的次数不好统计，所以放弃这种方式。

可以找一些参照变量，i和k。i从1开始一直增加到m，而k并不是每次for循环都会增加，所以，k累积增加的值肯定小于m。而while循环里k=next\[k\]。实际上是在减小k的值，k累积都没有增加超过m，所以while循环里面k=next\[k\]总的执行次数也不可能超过m。因此next数组计算的时间复杂度是O(m)。

**关于第二部分的时间复杂度**  
I从0循环增长到n-1,j的增量不可能超过i，所以肯定小于n。而while循环中的那条语句j=next\[j-1\]+1，不会让j增长的。因为next\[j-1\]的值肯定小于j-1，所以while循环中的这条语句实际上也是让j的值减少。而j总共增长的量都会超过n，那减少的量也不可能超过n，所以while循环中的这条语句总的执行次数也不会超过n，所以这部分的时间复杂度是O(n)。

所以综合两部分的时间复杂度，KMP算法的时间复杂度就是**O(m+n)**。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/185c6f61b90741ffbec6c7c0c75a0abf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/70a9569372504f89abb49fe9cdbb3131.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/164fd6cb85504028b9cbe447d7e29991.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/1645dc5f213445a5bafb835ade7c39c5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221123/cdcd134d98024082a325655e7a6ea4b1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221123/b0b99d8e6bca43d6a3b3f356800c7533.png