KMP算法

1，什么是kmp算法

kmp算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。简而言之就是在一串字符串中找寻一串子串。

基本思想：

设主串后面用m表示(长度为m)：a b a c a a b a c a b a c a b a a b b

模式串后面用n表示(长度为n)：  a b a c a b

如过使用暴力算法匹配模式串在主串的位置，则先是是m[0]，n[0]对比，一样下表就同时往后移一位，继续对比，如果不一样，此时m从第二位开始和n进行匹配，继续刚才的操作，直到找到为止，这种方式极大的降低匹配效率，时间复杂度为O(mn)。

kmp算法就是为了在比较中让模式串尽量右移，从而达到提高效率效果。假设m是个char[],n也是，m[i]和n[j]进行比较,如上图，前面五位都相同,第6位开始出现差异。此时我们就要向右移动n，那么要向右移动几位呢。我们看mn前面5位都是相同的,a b a c a 的前缀和后缀只有一个a是相同的。对应的m中前面五位也只有一个长度为一的前缀和后缀a,

所以我们将n整体右移到m[4]的位置，变成

a b a c a a b a c a b a c a b a a b b

            a b a c a b

当比较到第二位又出现不等的情况，此时的n右移一位就行比较，此时已经在m中找到了n所在的位置，然后将a的下表返回。这就是大概思路，这样比较我们只进行3次比对，就出了结果。时间复杂度为O(m+n)。

a b a c a a b a c a b a c a b a a b b

               a b a c a b

现在我们来看看n的移动规则怎么来的，其实就找abacab中每一位到前缀中存在的最大长度的相等的前后缀，分析一下

a b a c a b

用一个next[]来保存计算出的值，n[0]本来就是前缀，所以为next[0]=0，n[0],n[1]对比不相等,所以n[1]b的相同的前缀也为0,next[1]=0，然后n[0]和n[2]对比相同，所以next[2]就是n[0]在next[]中对应的下标next[0]+1，所以next[2]=1;此时n[0]就不需要在和后面对比，从第二位n[1]=b开始接着对比，n[1]和n[3]进行对比，不相等，此时代表ab和ac不相等了，所以我们的下标又要回退到n[1]的前一位也就是n[0]在next[]数组中所对应的值，所以现在是n[0]和n[3]进行对比ac不等，此时n[0]已经不能往前移动，所以n[3]对应的next[3]值为0，然后n[0]继续对比n[4]，aa相等，根据上面的分析得出next[4]=0+1(前缀a的下标加一)，前后a相等已经找到所以开始对比n[1]和n[5]为bb相等，所以next[5]=1+1(前缀b的下标加一)，最后得到next={0,0,1,0,1,2},在一次说明2的含义，就是存在一个长度为2相等的前后缀，这里就是ab;

代码如图

目标串 a b a c a a b a c a b a c a b a a b b

模式串 a b a c a b

next值 0 0 1 0 1 2 

第六位ab不等，b的前一位a的next值为1

目标串 a b a c a a b a c a b a c a b a a b b

模式串             a b a c a b

此时m[5]!=n[1],重复

以上步骤，b的前一位a的next值为0，继续右移，最后相等，返回a的坐标，这就是kmp算法了

目标串 a b a c a a b a c a b a c a b a a b b

模式串                a b a c a b