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]
如图:

代码如下:


