3张图理解KMP算法----------------------------------------KMP算法的简单理解
1.KMP。
例如：ababa（求next数组值）
从0开始
ab（默认0，1）
然后看最大匹配长度，也就是相同字符的最大匹配的长度（例如abab：最大匹配长度就是2（ab:ab））
还没有理解看看下图（最大匹配长度为3的next数组值）
所以next数组值分别为（0,1,1,2,3）
2.KMP算法的改进（主要是因为回溯得过多，造成不必要的时间开销了）
改进了就增加了一个nextval值
nextval第一个和第二个值照写
1. a的next值为1他就回到第一个位置处，而第一个位置处的next值为0所以他的nextval值也为0.如下图所示：
2.再看第四个数b，他的next值为为2，找到第二个元素，他的next值为1，找到第一个元素，由于第一个元素为a与b不同则，b的nextval值为1.
3.总结如下图所示.
所以这道题的答案为：
3.求字符匹配比较次数
我们以一道408考研的真题为例：
当匹配到第六位的时候，匹配失败
然后回去查找C的next值（3）
从模式串的第三位开始匹配，从主串的第六位开始匹配。
然后就匹配成功，一共比较次数为10次。
如下图