数据结构KMP算法详解

���录

1. KMP算法是什么？

2. KMP算法的由来

2.1 需要要解决的问题

2.2 一开始想到的方法

2.3 KMP算法诞生了

3.KMP算法的详解

4.KMP算法的实现

5.KMP算法的改进

1. KMP算法是什么？

• KMP算法是一种改进的字符串匹配算法，即可以快速的从主串中找到子串的算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。
• KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。

  2. KMP算法的由来

  2.1 需要要解决的问题

  我们在数据结构的“串”这一章中提到的问题：主串找子串这个问题，

  例如：现在我们有主串：arr1[ ] = "abababc"，子串：arr2[ ] = “abc”。

  2.2 一开始想到的方法

  我们一开始想到的是暴力求解，我们是将子串和主串逐一匹配，如果第一个字符相等就继续匹配第二个字符，直到子串与主串全都匹配成功，就返回子串的位置，一旦其中某两个字符匹配不成功，主串就回到开始匹配字符的下一字符，而子串回到第一字符。

  通过以上举例可以看出，传统的暴力求解，需要多次回溯，且第一个字符串和第二个字符串都需要回溯，明显回溯过去也一定是错的，那有没有什么办法让他回溯到特定的位置，不至于像暴力求解一样，产生许多不必要的步骤，于是就有了本篇的重点：KMP算法诞生了

  2.3 KMP算法诞生了

  KMP算法是一种改进的字符串匹配算法，即可以快速的从主串中找到子串的算法。

  3.KMP算法的详解

  （1）现在我们先看一个图：第一个长条代表主串，第二个长条代表子串，当发现指针指向的元素不匹配时，指针回溯到第一个元素，这个就是算法效率低的原因，称为幼稚的匹配算法。

  （2）现在我们看一下聪明的KMP匹配算法是什么样子的：下图还是当发现指针指向的元素不匹配时，移动模式窜，使前缀移动到后缀的地方

  （3）这一步弄懂了，KMP算法的精髓就差不多掌握了。事实上，每一个字符前的字符串都有最长相等前后缀，而且最长相等前后缀的长度是我们移位的关键，所以我们单独用一个next数组存储子串的最长相等前后缀的长度。而且next数组的数值只与子串本身有关。

  所以next[i]=j，含义是：下标为i 的字符前的字符串最长相等前后缀的长度为j。

  然后把他们放到一个数组中

  4.KMP算法的实现

  现在我们分析一下KMP算法的时间复杂度：

  KMP算法中多了一个求数组的过程，多消耗了一点点空间。我们设主串s长度为n,子串t的长度为m。求next数组时时间复杂度为O(m)，因后面匹配中主串不回溯，比较次数可记为n，所以KMP算法的总时间复杂度为O(m+n)，空间复杂度记为O(m)。相比于朴素的模式匹配时间复杂度O(m*n)，KMP算法提速是非常大的，这一点点空间消耗换得极高的时间提速是非常有意义的，这种思想也是很重要的。

  • 下面我们一起来欣赏计算机如何求得next数组的

    typedef struct{char data[MaxSize];int length;//串长} SqString;//SqString 是串的数据结构//typedef重命名结构体变量，可以用SqString t定义一个结构体。void GetNext(SqString t,int next[])//由模式串t求出next值{int j,k;j=0;k=-1;next[0]=-1;//第一个字符前无字符串，给值-1while (j