数据结构字符串匹配KMP算法的详解（题目讲解简单易懂）

向右看齐 2023-10-09 20:07 5阅读 0赞

> **有问题欢迎评论区私信留言交流~~~**

博主近来在复习数据结构的过程中遇到了KMP字符串匹配算法，在浏览了网上众多文章后感觉写的不够清晰和简单易懂，尤其是从做题的角度上来讲，下面就个人对KMP算法的理解进行解题，有问题还请谅解~

首先我们来看一下KMP算法的定义

## KMP算法定义 ##

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

KMP算法是三位学者在 Brute-Force算法的基础上同时提出的模式匹配的改进算法。Brute- Force算法在模式串中有多个字符和主串中的若干个连续字符比较都相等,但最后一个字符比较不相等时,主串的比较位置需要回退。KMP算法在上述情况下,主串位置不需要回退,从而可以大大提高效率

所以我们可以明确KMP算法的核心就是当一位字符串匹配失败后子串应该移动的距离，所以关键是要求出这个移动的距离，明确了我们的目标之后下面我们以具体的题目进行讲解

## 基本概念 ##

首先我们明确几个题目中要用到的基本概念

> 1：主串 就是要被匹配的串
> 
> 2：字串 也称模式串，用于匹配主串
> 
> 3：前缀
> 
> 4：后缀
> 
> 5：最长相等前后缀长度
> 
> 6：部分匹配值PM
> 
> 7：next数组
> 
> 8：nextval数组

想必大家看到上面如此多的概念难免头晕犯难，下面我们以具体的题目进行讲解，这个算法实际上非常好理解

前缀指的是除最后一个字符外，字符串的所有头部字串。后缀指的是除第一个字符外，字符串的所有尾部子串，部分匹配值即为字符串的前缀和后缀的最长相等前后缀长度

下面我们从一个具体的例子来求解以上概念

按照规则一个个求前后缀即可，**这里有一个小坑就是后缀是从往前的，所以是ba bab...**

![eb1f58e2dcc849ea9dcb6821009fa572.jpeg][]

那么上面的部分匹配值表中**某个字符不匹配时子串需要向后移动的位数计算公式如下**

> 移动位数=已匹配的字符数-对应字符的部分匹配值

**切记，此处查找的是最后一个匹配字符即下图b的部分匹配值**

方法如下图所示，其余字符不匹配方法相同，直至字符串匹配成功或匹配失败为止

![74f742fe47de4a53adb9bdb61e077ca8.png][]

**这里写错了 应该是b的部分匹配值为0**

那么问题来了，既然上面已经可以计算出移动位数，那么next和nextval数组又是什么呢？

因为上面的计算方法还是不够直观和简单，还要查找上一个字符的部分匹配值，所以我们进一步简化，**将PM表整体右移一位，就得到了next数组，第一个元素右移后空缺用-1填充，最后一个元素右移溢出不用理会直接舍去，有时为了计算方便也可以next数组值整体加1，这点应根据题目干条件灵活应对，其实串为序从1开始就整体+1，从0开始则不用加**

此时移动位数=已匹配字符数-对应部分的next数组值（即不用看上一位的部分匹配值）

所以上图中的next数组为-1 0 0 01 如果加1则为 0 1 1 1 2读者可自行验证

最后nextval数组就是对KMP算法的进一步优化，失配时如果Pj=Pnext\[j\]则会匹配相等的字符，解决办法是递归计算next\[j\]并将更新后的next\[j\]命名为nextval\[j\]，递归计算方法为

> nextval\[j\]=next\[next\[j\]\]

如果递归一次后仍然相等则继续递归，直至不等即可

**创作不易 觉得有帮助请点赞关注收藏~~~**

[Link 1]: https://baike.baidu.com/item/%E5%87%BD%E6%95%B0/18686609
[Link 2]: https://baike.baidu.com/item/%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6/1894057
[eb1f58e2dcc849ea9dcb6821009fa572.jpeg]: https://img-blog.csdnimg.cn/eb1f58e2dcc849ea9dcb6821009fa572.jpeg
[74f742fe47de4a53adb9bdb61e077ca8.png]: https://img-blog.csdnimg.cn/74f742fe47de4a53adb9bdb61e077ca8.png