传统从主串找子串方法
然子串从第一个开始，一个个比对，相同比对第二个字母
不同然子串后移一位重新开始比较
直至找到全部相同的或者主串里面没有让子串比较的字母了
这样的算法太暴力，执行效率太低
KMP算法
来说我们人脑对于字符串匹配的思考方式吧
从左往右直接扫
不会说回去再看一遍
那怎么让代码完成这样的操作呢？
那就是KMP算法喽
回溯子子串不回溯主串
直接右移五步
若11是g
若11不是j
但是到底子串要从主串的哪个位置开始比较是不固定的
如果死第五个字母不匹配
要从第四个字母开始比较
而不是从不匹配的字母开始匹配了
那么如果比较失败到底从主串哪里重新开始匹配呢？
需要另外定义一个next数组看到第几个不匹配然后
在取对应数字next数组的元素
子串的对应位置开始再次比较
（因为主串指针不回溯，所以next里面是存放的是子串的位置）
j是指向子串的从1开始
i指向主串
对应代码
next[1]=0;
第一个位置就不同，使j=0
然后i++，j++
子串重新指到1
然后主串后一一位
那么如何求一个模式串的next数组呢？
求next数组
手算
当j=6匹配失败应该从第个开始？
就拿子串依次次往后移呗
看有没有可以和前面对应的
对应了i个那么next[j]=i+1
对应了（此时j还是6）
对应了2个那么next[6]=3
这个也是同理
总结（方法）
比如说下面
第7个字符匹配失败，然后把对应的第1-6字符组成一个字符串
看这个字符串前缀和对应上面1-6进行匹配
一定是看对应的
上面串的后缀
和
下面串的前缀
（上面不含头，下面不含尾）最长相等长度哦
（就是让下面的往右移直至到第一次相同，就是最长长度，不包含刚开始的时候）
如果都不匹配，那就是0+1=1呗
一些特殊情况
如果一开始就不匹配（第一个位置）
那么next[1]固定是0，这个情况下实行i++和j++
如果第二个不匹配
这个时候其实取
1-j-1元素那就是第一个元素
就一个元素
这个元素既是前缀又是后缀
但是要求不能包含下面串的后缀
所以
此时next[2]=1（固定的）
我的一些小方法
就是看第i个匹配失败
取出对应模式串1-i-1（取两次）
然后和自己比较
看1-i-1
比如
ababaa
第三匹配失败
取
ab
ab
上面取后缀，下面前缀
下面往右移
abab
还是不相同
abab
最后没有相同的，重新开始比较呗
next[3]=1
比如第四个失败
取的是
aba
aba
下面的开始右移
abaaba
不同
abaaba
此时对应位置相同了
则next[4]=1+1=2
代码实现
时间复杂度
进一步优化
例如这个情况
下一步就是把j=1
这个过程有没有感觉有一丝多余
因为你的子串第四个字符和第一个字符就相同
第四个不匹配
所以主串的对应字符不是g
所以你就算把j=1然后比较也肯定不相同
这就多了一次比较
对应优化
怎么求next_value
看左下角
首先有next数组
然后从左往右比
看从2开始看
第二个序号j的next
指向第一个字符（a）
但是它自己对应也是a
所以把对应第一个序号对应的数组（0）
赋给第二个序号对应的nextvalue
第三个也是
第四个也是
第五个的话对应的next为4
第四个字符和第五个字符不同
所以
保存对应的next到nextvalue
