KMP模式匹配算法
模式匹配算法是字符串模式匹配中一个比较好的算法，但是学起来非常的费解，特别是next数组的产生过程让人有点摸不着头脑。现在尝试对这个方法进行深入的了解，以求熟练掌握这一算法思想。
KMP算法又叫克努特-莫里斯-普拉特操作，是由这三个人发明的。其中的克努特就是《计算机程序设计的艺术》这本书的作者，也是软件界巨匠式的人物。
KMP算法的基本思路是：每当一次匹配过程出现字符比较不等时，不需要回溯i指针，而是利用已经得到的“部分匹配”的结果将模式串“向右”滑动尽可能远的一段距离后，继续进行比较。
需要解决的问题是：当匹配过程中产生“失配”（即si <> pj）的时候，模式串“向右滑动”可行的距离多远，也就是说，当珠串中第i个字符与模式串中第j个字符“失配”时，主串中第i个字符（i指针不回溯）应与模式中哪个字符再比较？（这个才是模式匹配算法的难点所在）
尽管这个地方有一定的难度，但是大牛们从数学和逻辑的角度进行了分析。这个分析的过程是非常重要的，按照严蔚敏的书上说的，大致是这样的过程：
由此可以引出模式串的next函数的定义
转载于:https://www.cnblogs.com/superhuake/archive/2012/05/08/2490709.html