kmp算法笔记（简单易懂）
一般字符串比较长串m短串为n，那么用暴力方法复杂度为O(m*n)
但是kmp却可以达到O(m+n)！！！！！！
对于这个神奇的算法，我也是似懂非懂，
下面介绍一个简单的方法求kmp
1、求next数组
这个数组时kmp的灵魂！next数组时对于短串n求的
步骤：
1）next[0]=-1
2) next[i]=前面的字符串中最大公共子串长度
例子：
设m串为：a b a b c， 串长为5，那么next数组长度为5，下面是对应的next数组
可以看到，b下面有一个1，这个1是怎么得来的呢？》》是根据前面aba这个串得来的，aba串的最大公共子串长度为1
aba最大公共子串是a，因为从左边数连续的最大子串（小于母串长度）是a，从右边数连续最大子串也是a，所以next【3】=1
c下面的2是由于前面的串abab的最大公共子串长度为2（公共子串为ab）
再比如aaaa最大公共子串长度为3（从左边连续最大子串=从右边连续最大子串=aaa）
2、使用next数组，和长串n短串m进行匹配
1、首先前三个都匹配上了，但是到箭头处不匹配了，下面进行m串移动
2、移动后如下图
怎么移动的呢？
由于a和b不匹配所以m串右移，看next数组对应的b下面的值为1，那么是把m串的下标为1的位置和箭头对齐。
现在继续从箭头处向后比较，发现不匹配，再移动》》看到对应b下的值为0，那么把m串下标为0的位置和箭头对其
依旧不匹配，再移动，此时a对应下标为-1，但是数组没有-1的位置，其实这里-1的位置与箭头对其就等价于m串右移一维，注意这里要多做一个操作，就是比较的位置向后移动一位，如果此时n串下标在箭头处为j，那么执行j++，相对的m串执行i++，如下图
继续比较
可以看到，箭头走到了m串的末尾，匹配到了！！
3、可以看到匹配到了，如果后面还有子串m那么将继续寻找，移动m串使得下标为2的位置对其箭头，不匹配查询结束。
这里仅仅介绍原理和方法，代码网上有很多就不展示了，下面是哔哩哔哩上的视频教程，如果没有明白可以看看视频连接附上（https://www.bilibili.com/video/av52365939/?spm_id_from=trigger_reload）