一 引言
先不说kmp算法，先谈谈朴素的模式匹配算法。朴素的模式匹配算法是一种暴力匹配算法，也就是最蠢的匹配算法。如果失配的话，i,j都得变，i回溯至刚开头字符的下一位，j就置为0。这就造成了浪费，因为i已经回溯到刚才比较过了的字符，又需要再一次被比较，重复比较，造成浪费。如果i不动，只动j的话是不是可以呢。这就引出了kmp算法的精髓了。kmp算法就是保持i不动，通过修改j的位置，让模式串尽可能的移动到需要的地方。
二 补充一些知识（前缀，后缀,部分匹配值，部分匹配表）
这些东西都可以先不看，后面说到了再来看。
"前缀"指除了最后一个字符以外，一个字符串的全部头部组合；
"后缀"指除了第一个字符以外，一个字符串的全部尾部组合
废话少说，举个例子："ababa"
| 前缀 | 后缀 |
| a | baba |
| ab | aba |
| aba | ba |
| abab | a |
"部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。以"ABABA"为例，
－ "A"的前缀和后缀都为空集，共有元素的长度为0；
－ "AB"的前缀为[A]，后缀为[B]，共有元素的长度为0；
－ "ABA"的前缀为[A, AB]，后缀为[BA, A]，共有元素为"A"，共有元素的长度1；
－ "ABAB"的前缀为[A, AB, ABA]，后缀为[BAB,AB, B]，共有元素为"AB"，共有元素的长度为2；
－ "ABABA"的前缀为[A, AB, ABA, ABAB]，后缀为[BABA, ABA, BA, A]，共有元素为"ABA"，长度为3；
部分匹配表
next数组的作用就是用来记录某个字符失配时j应该赋的值。与部分匹配值有关系。
看图。
也就是说next的值由部分匹配值整体向右移一位，且在第一位赋值-1后，再整体加1而成。
三、解释为什么要用next数组的疑惑。
先看下面图的分析:
先看左上角的表，再看右下的文字。
注意，这图省略了文本，也就是说i自行想象。
文字有点绕，但总的来说，10号‘a’失配，只看左上角的表就也知道应该把123号放到789号，让第4号字符去和待匹配的字符去匹配。
如果上面能明白，那就接着往下走，下面抽象的来了。
把最上面的逻辑搞清楚了，跟着脚步走就行了。
如果你不信这公式:那就举个具体的例子，让你相信（这个算法本身还是有瑕疵，但总比暴力好!）上图。
