https://leetcode-cn.com/problems/implement-strstr/

KMP

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

实质：因为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位置开头的

接下来我们来过一下例子理解一下
- 这其中隐含着第二个原理：图中i到j位置这段每个位置开头的是一定配不出这个match的
kmp怎么加速的？当以一个i位置开头的匹配失败了，则找到右边离i最近的一个靠谱的位置
现在就来证明（我们就假设以i~j这段位置中开头的能配出match的话，会发生什么情况，进而反证）
- 要是图中以k位置开头的能配出match的话，至少图中k~x这段长度对应的match等量长度应该相等（也就是图中画的两个椭圆blue长圈），但这就推出一个矛盾来了，
  - 我之前求的next数组中y位置的指标是5，你现在告诉我你找出了个更长的长度？（逗我呢？）
- 现在给一个例子，然后自己在把这个流程多走几遍, 看看多失败几次是什么样
  - str aabaactaabaa5
  - match aabaactaabaak
  - 如果y跳到了0位置（在x和y位置的值不等的情况下），说明配不出来了，x赶紧换下一个

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

人为规定0位置是-1， 1位置是0，从i = 2位置怎么求？若0位置和1位置相等，则是1，否则0
然后就可以从左求到右了，流程如下
- 、
- 假定现在 i - 1位置的信息已经求到了是7，怎么求i ？判断7位置的值和i - 1位置的值是否相等，若相等，那么i位置的信息就是8， 而且最长只能是8，为啥？证明（假设可以再长，比如9）
  - 如果是9，那么也可以说0~7 和i-9 ~i-2这段长度为8的相等，那不就推出i-1位置的信息为8了嘛，就和之前我们求的答案7矛盾了
- 回到上上上面，若不相等，则再往前跳
  - 有点抽象，举个例子
    - 7位置和i-1位置不相等，然后
    - 看3位置和i-1位置相等不？若相等，那么i位置的信息就是t位置的信息（3）+1 = 4, 若不相等，则、、
    - 看1位置和i-1位置相等不，若相等，则i位置的信息就是1+1 = 2，若不相等则
    - 看0位置和i-1位置相等不，若不相等，就说明i位置的信息是0 ```java public static int getIndexOf(String s, String m){ if (s == null || m == null || m.length() < 1 || m.length() > s.length()) { return -1; } char[] str = s.toCharArray(); char[] match = m.toCharArray(); int[] next = getNextArray(match); int x = 0; int y = 0; while (x < str.length && y < match.length) { if (str[x] == match[y]) { x++; y++; } else if (next[y] == -1) { // y==0 x++; } else { y = next[x]; } } // x越界 y不越界 -1 // x不越界， y越界 // x越界， y越界 return y == match.length ? x - y : -1; }

public static 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; // cn代表，cn位置的字符，是当前和 i-1位置比较的字符 int cn = 0;
while (i < match.length) { if (match[i - 1] == match[cn]) { next[i++] = ++cn; } else if (cn > 0) { cn = next[cn]; } else { next[i++] = 0; } } return next; } ```

KMP算法

https://leetcode-cn.com/problems/implement-strstr/

KMP