KMP算法——俗称看毛片算法

た入场券 2022-03-08 10:44 89阅读 0赞

咳咳咳，这是看毛片算法的简单介绍  
首推一个博客，这个博客很优秀，我的KMP算法就是从上面学来的——[https://www.cnblogs.com/yjiyjige/p/3263858.html][https_www.cnblogs.com_yjiyjige_p_3263858.html]

## 算法思想 ##

假设母串是BACAACAAADH，子串是ACAACAD，  
当匹配到下图一步，指针i和j的位置明显不匹配了，  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdU1hbmc5NDM4_size_16_color_FFFFFF_t_70]  
肿么办，按照暴力的办法应该是把指针i和j回溯到如下图的位置再比较  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdU1hbmc5NDM4_size_16_color_FFFFFF_t_70 1]  
但是，我们发现这样时间复杂度就变得很不友好，  
细心或者对KMP有接触的朋友应该注意到了其实可以不回溯这么远，  
其实可以回溯到如下图的位置  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdU1hbmc5NDM4_size_16_color_FFFFFF_t_70 2]  
为什么呢，因为在子串中存在前三个字符和接下来的三个字符相同，  
这样，我们就可以保持i指针不变，将j指针回溯三个字符，然后接着继续进行匹配操作，  
从这个例子可以看出子串中有可能存在和开头相等的子子串，式子表示如下  
str.substring(0, k) = str.substring(m, n)  
我们可以利用这个特性，减少已经匹配过的串尽量少的回溯  
咳咳咳，先想清楚再看下面的，如果想不太明白，那也看看下面的，  
下面的是重点，考试要考的  
\++++++++++++++++++++++++++华丽的分割线++++++++++++++++++++++++++++  
弄明白KMP的主体思想思想之后，我们就开始关注怎么实现了，  
首先先看一个例子，如果当出现如下匹配失败的时候  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdU1hbmc5NDM4_size_16_color_FFFFFF_t_70 3]  
因为橙色区域的和黄色区域的已经确认匹配，并且存在相等的情况，  
所以回溯的时候，可以保持指针i不变，将指针j回溯到黄色区域的开头那里，如下图  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdU1hbmc5NDM4_size_16_color_FFFFFF_t_70 4]  
也就是下图  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdU1hbmc5NDM4_size_16_color_FFFFFF_t_70 5]  
也就是回溯到的位置是下标为3的位置，从这个例子可以看出，  
在母、子串匹配的时候，无论在哪个位置不匹配，都会存在一个回溯的值，  
哪怕是第一个就不匹配，也可以**回溯到-1的位置**。  
下面那个就是对应位置回溯位置的数组  
对于ACAACAD这个子串来说，其数组为  
![在这里插入图片描述][20190315002243631.png]  
关于代码怎么实现的，这个目前比较流行的是我下面给出的代码，  
这个代码有两个难点，一个是k = next\[k\]，一个j–  
结合我给的例子，慢慢揣摩就能明白，我抽象表达能力不太好，这里就不误导大家了，  
大家也可以去看看我开头推荐的那个博客，ta写的挺详细的，但是我没看（主要是太笨了，不想看也看不懂），我都是看ta代码慢慢研究出来的

## 上代码 ##

// 暴力匹配的算法，至于怎么暴力，反正就是暴力，不要在意这些细节嘛
    public int indexOf(String origin, String subStr) {
        int result = -1;
        for (int i=0; i<origin.length()-subStr.length(); i++) {
          boolean matching = true;
          for (int j=0; j<subStr.length(); j++) {
            if (origin.charAt(i+j) != subStr.charAt(j)) {
              matching = false;
              break;
            }
          }
          if (matching) {
            result = i;
            break;
          }
        }
        return result;
      }

// KMP算法的实现
    public int indexOf(String origin, String subStr) {
        int result = -1;
        int i, j;
        i = j = 0;
        int[] next = getNext(subStr);
        while (i < origin.length()) {
          // 相等的情况
          if (subStr.charAt(j) == origin.charAt(i)) {
            i++;
            j++;
            if (j == subStr.length()) {
              result = i - j;
              break;
            }
          } else {  // 不等的情况
            j = next[j];
            if (j == -1) {
              i++;
              j = 0;
            }
          }
        }
        return result;
      }
    
    // 获取next数组
      public int[] getNext(String str) {
        int[] next = new int[str.length()];
        int k = next[0] = -1;
        // 其它博客都是while循环，这里为了体现j--这个的功能，就不用while了
        for (int j=1; j<str.length(); j++) { 
          if (-1 == k || str.charAt(j-1) == str.charAt(k)) {    // 第一次k不等于-1的时候是j=2的时候
            next[j] = ++k;
          } else {    // ACAACADH
            k = next[k];
            j--;    // 懂了这个就懂了整个算法
          }
        }
        return next;
      }

## 时间复杂度 ##

O(m+n)

> 这个博主很懒，就写了这么多，并且博主智商捉急，肿么办，挺急的单就不在线等了，忙着找药，有事留言

[https_www.cnblogs.com_yjiyjige_p_3263858.html]: https://www.cnblogs.com/yjiyjige/p/3263858.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdU1hbmc5NDM4_size_16_color_FFFFFF_t_70]: /images/20220308/9cda28dddc334dde92374e0a9c655978.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdU1hbmc5NDM4_size_16_color_FFFFFF_t_70 1]: /images/20220308/69d52c28dd9947b7bf8b82f2f3560fe3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdU1hbmc5NDM4_size_16_color_FFFFFF_t_70 2]: /images/20220308/43e52cc892a84a5ebb4ef11b7a23e799.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdU1hbmc5NDM4_size_16_color_FFFFFF_t_70 3]: /images/20220308/29bf44e6d3e244399dd35902a7eb4b3b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdU1hbmc5NDM4_size_16_color_FFFFFF_t_70 4]: /images/20220308/b496797a8abe4fcdbe9cc84400903a98.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdU1hbmc5NDM4_size_16_color_FFFFFF_t_70 5]: /images/20220308/2c322668e4e049d4a01756cda42a08d1.png
[20190315002243631.png]: /images/20220308/45bde4413c754f96b88501051e3db75b.png