KMP算法

先简单解释下KMP是用来干嘛，简单来说就是解决的问题就是在字符串中的模式定位问题。
直接举例吧
目标串s="aaaaab",模式串t="aaab"，看道这里有的人肯定会想，这么简单，暴力一下不就出来了。但暴力也只是适用于数据小的情况下，而KMP算法就是起到了消除主串指针的回溯，从而使算法效率得到提高。
那它是如何提高的呢？其实就是用了一个next数组把模式串t中的每个位置信息保存下来，具体保存了什么信息，我们看下图：

我们可以看到 因为s[3]!=t[3] 所以 重新匹配 但我们从t中发现：b前面有两个字符和开头的两个字符相同 即用next数组保存信息 next[3]=2,所以不难看出 t中每个位置都能有一个next[i]来保存。用张图来总结就是：

接下来用四张图 来分析下next[i]的几种意思（图中有解释）

所以 综上所诉 我们可以得到模式串t求next的算法 即

有人可能会问 为什么是while(j<t.length-1) 其实这里我们是用了next[j]求next[j+1] 所以j的取值范围为0~t.length-2。去个例子：
t="aaaac" 不难求出next[3]==2 k==2,又因为j==3 k==2 所指字符相同 所以就有j++ k++ 进而得到next[4]=3(如图）

在举个例子吧 直接上图
(可以试着自己多举例模拟下）
把求next[i]理解好了 那KMP算法也就懂了大部分了 接下来我们讲下KMP过程（本来打了一大段文字来解释的 但本人归纳总结嫩个里太差 讲诉的比较繁琐 所以还是用代码 配上注释比较容易理解）

刚学KMP不久 掌握的还不是很透彻 基本上是根据老师所讲和自己的理解所写 若有错误或者其它见解 欢迎指出 讨论