https://leetcode-cn.com/problems/implemen t-strstr/

暴力解： 以每个位置 i 为开头，逐个匹配，若不能匹配，则以i + 1位置为开头，重新匹配………

KMP

  • KMP算法其实和暴力解流程一样，只不过有加速，也是以每个位置为开头看能不能配出match串
  • 每个位置都有一个指标(和自己无关)——>它之前这坨字符串的前缀和后缀的最长相等长度(注意：一定不要取到整体)
    • image.png
  • 了解了这个指标的含义后
  • 接下来我们先对match字符串的每个位置都求一下这个指标，应该得到的是一个数组（人为规定零位置的信息为 -1， 一位置的信息为0，表示不存在, 这个数组就是next数组，
  • 我们先假定我们已经有了这个数组，看这个next数组对kmp这个算法匹配过程中会产生如何强的加速效果，梳理完后，我们再回过头来看这个next数组如何优雅的生成
  • 假定现在它俩一路比下来比到x和y位置不相等了（若是暴力方法，接下来他们将从i + 1和1位置重新开始比对，那kmp呢？）
    • 就要用到next数组了
    • image.png
    • image.png

      x不用动，只用y跳，然后和x重新比对 (这么做的实质是啥？)

image.png

实质： 因为str和match是一路比下来直到x和y位置才不等的，所以A(图中X往左5) 和B（图中Y往左5 —>j 位置）是相等的，然后又根据next数组中Y位置的信息，知道B和C是相等的，所以A和C相等，所以A和C这段不用验也知道他们相等，因此我就可以在str中以j开头的位置和match比较了，也就是现在X和现在的新Y去比对 ———> 求的是以j位置开头的

image.png

  • 接下来我们来过一下例子理解一下

    • image.png

      这其中隐含着第二个原理： 图中i到j位置这段每个位置开头的是一定配不出这个match的

  • kmp怎么加速的？ 当以一个i位置开头的匹配失败了，则找到右边离i最近的一个靠谱的位置

  • 现在就来证明（我们就假设以i~j这段位置中开头的能配出match的话，会发生什么情况，进而反证）

    • image.png

    • 要是图中以k位置开头的能配出match的话，至少图中k~x这段长度对应的match等量长度应该相等（也就是图中画的两个椭圆blue长圈），但这就推出一个矛盾来了，

      • image.png
      • 我之前求的next数组中y位置的指标是5，你现在告诉我你找出了个更长的长度？（逗我呢？）

    • 现在给一个例子，然后自己在把这个流程多走几遍, 看看多失败几次是什么样

      • str aabaactaabaa5
      • match aabaactaabaak
      • 如果y跳到了0位置（在x和y位置的值不等的情况下），说明配不出来了，x赶紧换下一个

接下来就是求next数组的问题了

  • 人为规定0位置是-1， 1位置是0， 从i = 2位置怎么求？ 若0位置和1位置相等，则是1，否则0

  • 然后就可以从左求到右了，流程如下

    • image.png、
    • 假定现在 i - 1位置的信息已经求到了是7，怎么求i ？ 判断7位置的值和i - 1位置的值是否相等，若相等，那么i位置的信息就是8， 而且最长只能是8，为啥？证明 （假设可以再长，比如9）
      • image.png
      • 如果是9， 那么也可以说0~7 和i-9 ~i-2这段长度为8的相等，那不就推出i-1位置的信息为8了嘛，就和之前我们求的答案7矛盾了

    • 回到上上上面，若不相等，则再往前跳

      • image.png

      • 有点抽象，举个例子

        • image.png
        • 7位置和i-1位置不相等，然后
        • 看3位置和i-1位置相等不？若相等，那么i位置的信息就是t位置的信息（3）+1 = 4, 若不相等，则、、
        • image.png
        • 看1位置和i-1位置相等不，若相等，则i位置的信息就是1+1 = 2，若不相等则
        • image.png
        • 看0位置和i-1位置相等不，若不相等，就说明i位置的信息是0 ```java // KMP算法 public int strStr(String haystack, String needle) { if (haystack == null || needle == null || needle.length() > haystack.length()) { return -1; } if (needle.length() == 0) { return 0; }

        char[] str = haystack.toCharArray(); char[] match = needle.toCharArray(); int[] next = getNextArray(match); int x = 0; int y = 0; while (x < str.length && y < match.length) {

        1. if (str[x] == match[y]) {
        2.     x++;
        3.     y++;
        4. } else if (next[y] == -1) { // y跳到0位置了
        5.     x++;
        6. } else {
        7.     y = next[y];
        8. }

        } /* y不越界， x越界， -1

        • y越界， x不越界
        • y越界， x越界
        • */ return y == match.length ? x - y : -1; }

      private int[] getNextArray(char[] match) { if (match.length == 1) {

         return new int[]{-1};

      } int[] next = new int[match.length]; next[0] = -1; next[1] = 0; int i = 2; int cn = 0; while (i < match.length) {

         if (match[cn] == match[i - 1]) {
       next[i++] = ++cn;
   } else if (cn > 0) {
       cn = next[cn];
   } else {
       next[i++] = 0;
   }

      } return next; } ```