前言
KMP算法是为了字符串匹配问题而被研究出来的，字符串匹配问题就是查看一个字符串A是否是字符串B的子串，如果是字串的话，在B的哪个位置？此算法代码简练，但理解起来非常困难，建议挑出一整块时间来专门学习，本文作者写的非常用心，还不了解KMP的小伙伴一定要静下心来慢慢细品，你一定会有所收获🍊
一、字符串匹配问题
如果遇到这种在一个字符串中寻找另一个字符串的子串这种问题，大多数人第一时间想到的肯定是通过暴力匹配算法来完成，也就是Brute-Force算法简称BF算法，时间复杂度为O（m*n）,如果有上千行上万文本呢？，时间成本一定会很高，所以D.E.Knuth，J.H.Morris和V.R.Pratt三位大神提出了KMP算法，KMP（Knuth-Morris-Pratt ）算法也由他们三个的名字命名。
1.BF算法
2.KMP算法
肉眼可见的差距
二、next数组
next数组是KMP算法的精髓
KMP之所以会这样高效的查找字符串全都是next数组的功劳，也就是动图中字符串下面的数字，KMP算法会根据生成的next数组来移动，如果比对错误，将子串的首位直接移动到主串对比错误的位置，随后根据next数组提供的下标向左移动x格，图中下标为-1，所以向左移动-1格，就是向右移动一格
三、手写nex思想
注：上面图片的下标是按照nextVal生成的，next数组生成请看下面，nextVal是next的改进版，后面会讲到，我们先理解next数组生成原理
next数组的值计算的是从第n位开始前面字符串的最大公共前后缀的长度，不包括整个字符串本身，比如有这样一个字符串
从第一位向前看，没有字符，没法求，所有人为规定next[0]固定为-1（这里也有部分老师讲解第一位是0，其实思想都一样只不过是下标不一样而已，我们学的是思想不用在意这些），从第二位b向前看，也没有公共前后缀，next[2]为0，从第三位c向前看，也没有，next[3]为0，第四位a向前看，也没从第一位向前看，没有字符，没法求，所有人为规定next[0]固定为-1（这里也有部分老师讲解第一位是0，其实思想都一样只不过是下标不一样而已，我们学的是思想不用在意这些），从第二位b向前看，也没有公共前后缀，next[2]为0，从第三位c向前看，也没有，next[3]为0，第四位a向前看，也没
四、机算next思想
比如一个字符串abcda，此时next数组的最大公共前后缀是1，那如果加个b呢，abcdab，此时最大公共前后缀是2，加个c呢，最大公共前后缀就变成3，经过大量数据观察，发现每次最大公共前后缀最多+1。
如果一个字符串abcdeffabcde，此时最大公共前后缀是3，如果在后面加一个g，这个字符串变成abcdffabcdg，最大公共前后缀直接就变成了0，也就是说每次最大公共前后缀可能直接减少到0。
如果增加一个字符的时候，发现新增加的字符与前缀后面的字母不相同了，就会进行减少，如下图所示，一次次进行查找，当前新的最大相同前后缀是什么，直到查找到位置。
这种方法未免有些麻烦，我们可以利用已有的条件进行优化，如果没有找到，直接找到其对应的next数组的值的字符串的下标，进行比对，如果成功，将找打他的next数组的值进行+1，就是next数组最新一位的值，如果找到最后，会找到字符串下标为0的位置，0位置的next数组值是-1，拿到-1的话数组会报错，这里写代码的时候不要忘记处理。
为什么可以这么做呢？因为前面红框的前缀，等于后面红框的后缀，我们在此基础上向后进行对比一位即可判断出next数组最新一位的值。
