数据结构笔记--KMP算法简单理解
KMP算法中的函数值只和模式串有关，而和相匹配的主串无关。
例 主串：a c a b a a b a a b c a c a a b c
模式串：a b a a b c a c
1.首先，我们给模式串标上序号
2.之后，我们把模式串的所有前缀依次列出来（虽然前缀不能为串本身，但在这里我么也将其列在最后面）
3.接下来，我们要求得每一个子串中相等的前缀与后缀的最大长度
我们拿第五个子串作为例子
可以看出，这条子串有相同的前缀后缀：ab 长度为2
123步示意图
4.这样，我们就得到了一组序列，但是这并不是我们要的next数列，我们暂且把它叫做maxL数列
5.接下来我们将maxL数列复制一行，去掉最后一个值，在开头加上一个-1，往右平移一格，每个值+1，这就是我们想要的next数列
6.接下来来看nextVal数列
- 首先，第一个值填为0；
- 序号依次检查maxL值和next值是否相等，若不相等，填入对应的next值；
- 若相等，填入对应序号为next值得nextVal值
7.这样，我们就得到了nextVal数列。