KMP算法

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的.时间复杂度为：O(m+n)

如下题目，目标串：x=ababcabcbababcabacaba     模式串：y=ababcaba   模式串Y能够在目标类是否完全匹配。 如下

上面我把X与Y每个元素进行匹配， 如果相等i++,j++, 但是当i的指针指向元素c，j的指针指向元素a时，就不匹配了，  如下往下 匹配  i++ 那么指针j该在哪个位置呢， 通过y字符串观察， 指针j应该移尾部的第二个a元素上， 如图

通过上面的规律，可以得到结果 就是如果目标串 与模式串进行匹配，决定i指针的位置， 我只要处理模式串内的 首尾是否有相同的， 来确定指针j的位置。 如下图

上图所得出结论是首部ab和尾部ab相同，所以j=1 指向B元素位置 如图：

以上图的结论， 我只有处理模式串y内部匹配，就可以得到指针j的位置， 那么在处理Y串时，首先是复制Y串，假设复制的串为Z

next[]是用来帮助我们找到回退的次数的，   i和j指针表示Y串和Z串的位置， 在Y串和Z串进行匹配， 需要三个操作1、next[i]=j (i最初的位置为1， j最初的位置为0）  先把指针j填到表中 ，2、i++,指针i前后移动一位，3、y串的i位置上字符与Z串j位置字符进行比较， 相等则j++, 不相等则 j=next[j-1]. 再执行3操作之后再 执行1操作，  知道i移动到最后一位，整个匹配结束， 最后next数组存的元素为next[0,0,1,2,0,1,2,3]

如图：

代码如下：