文档介绍：KMP算法
有动画，建议下载后观看
有这样一个字符串：
BBC ABCDAB ABCDABCDABDE
我想知道，里面是否包含另一个字符串
ABCDABD
BBC ABCDAB ABCDABCDABDE
ABCDKMP算法
有动画，建议下载后观看
有这样一个字符串：
BBC ABCDAB ABCDABCDABDE
我想知道，里面是否包含另一个字符串
ABCDABD
BBC ABCDAB ABCDABCDABDE
ABCDABD
首先，字符串"BBC ABCDAB ABCDABCDABDE"的第一个字符与搜索词"ABCDABD"的第一个字符，进行比较。因为B与A不匹配，所以搜索词后移一位。
BBC ABCDAB ABCDABCDABDE
ABCDABD
首先，字符串"BBC ABCDAB ABCDABCDABDE"的第一个字符与搜索词"ABCDABD"的第一个字符，进行比较。因为B与A不匹配，所以搜索词后移一位。
因为B与A不匹配，搜索词再往后移。
BBC ABCDAB ABCDABCDABDE
ABCDABD
就这样，直到字符串有一个字符，与搜索词的第一个字符相同为止。
接着比较字符串和搜索词的下一个字符.
BBC ABCDAB ABCDABCDABDE
ABCDABD
还是相同。
BBC ABCDAB ABCDABCDABDE
ABCDABD
直到字符串有一个字符，与搜索词对应的字符不相同为止。
BBC ABCDAB ABCDABCDABDE
ABCDABD
这时，最自然的反应是，将搜索词整个后移一位，再从头逐个比较。
BBC ABCDAB ABCDABCDABDE
ABCDABD
这样做虽然可行，但是效率很差，因为你要把"搜索位置"移到已经比较过的位置，重比一遍。
那么我们想什
么办法来解决这一问题呢？
BBC ABCDAB ABCDABCDABDE
ABCDABD
一个基本事实是，当空格与D不匹配时，你其实知道前面六个字符是"ABCDAB"。KMP算法的想法是，设法利用这个已知信息，不要把"搜索位置"移回已经比较过的位置，继续把它向后移，这样就提高了效率。
怎么利用这个已知信息呢？
可以针对搜索词，算出一张《NEXT值表》，即失败指针。
这张表是如何产生的，等下再介绍，这里只要会用就可以了。
已知空格与D不匹配时，前面六个字符"ABCDAB"是匹配的。查表可知，字符D对应的“NEXT值"为2，因此按照下面的公式算出向后移动的位数：
移动位数 = 已匹配的字符数 - 对应的NEXT值
BBC ABCDAB ABCDABCDABDE
ABCDABD
因为 6 - 2 等于4，所以将搜索词向后移动4位。
BBC ABCDAB ABCDABCDABDE
ABCDABD
因为空格与Ｃ不匹配，搜索词还要继续往后移。这时，已匹配的字符数为2（"AB"），C对应的“NEXT值"为0。所以，移动位数 = 2 - 0，结果为 2，于是将搜索词向后移2位。
BBC ABCDAB ABCDABCDABDE
ABCDABD
因为空格与A不匹配，0-(-1)=1，所以继续后移一位。
BBC ABCDAB ABCDABCDABDE
ABCDABD
逐位比较，直到发现C与D不匹配。于是，移动位数 = 6 - 2，继续将搜索词向后移动4位。
BBC ABCDAB ABCDABCDABDE
ABCDABD
逐位比较，直到搜索词的最后一位，发现完全匹配，于是搜索完成。如果还要继续搜索（即找出全部匹配），移动位数 = 7 - 0，再将搜索词向后移动7位，这里就不再重复了。
下面介绍《NEXT值表》是如何产生的。
第一位的next值必定为-1；
计算第n个字符的NEXT值：
-1个字符对应NEXT值，设为a；
-1，将第n-1个字符与第a个字符比较
，第n个字符对应的NEXT值为a+1
，令a等于第a个字符的NEXT值，执行第第2步。
-1，若为-1，则第n个字符next值为0
KMP代码实现
作NEXT值表：
//传入模式串与NEXT的空数组
//循环给每一个字符的next赋值
KMP部分：
END