有问题欢迎评论区私信留言交流~~~
博主近来在复习数据结构的过程中遇到了KMP字符串匹配算法，在浏览了网上众多文章后感觉写的不够清晰和简单易懂，尤其是从做题的角度上来讲，下面就个人对KMP算法的理解进行解题，有问题还请谅解~
首先我们来看一下KMP算法的定义
KMP算法定义
KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)
KMP算法是三位学者在 Brute-Force算法的基础上同时提出的模式匹配的改进算法。Brute- Force算法在模式串中有多个字符和主串中的若干个连续字符比较都相等,但最后一个字符比较不相等时,主串的比较位置需要回退。KMP算法在上述情况下,主串位置不需要回退,从而可以大大提高效率
所以我们可以明确KMP算法的核心就是当一位字符串匹配失败后子串应该移动的距离，所以关键是要求出这个移动的距离，明确了我们的目标之后下面我们以具体的题目进行讲解
基本概念
首先我们明确几个题目中要用到的基本概念
1：主串 就是要被匹配的串
2：字串 也称模式串，用于匹配主串
3：前缀
4：后缀
5：最长相等前后缀长度
6：部分匹配值PM
7：next数组
8：nextval数组
想必大家看到上面如此多的概念难免头晕犯难，下面我们以具体的题目进行讲解，这个算法实际上非常好理解
前缀指的是除最后一个字符外，字符串的所有头部字串。后缀指的是除第一个字符外，字符串的所有尾部子串，部分匹配值即为字符串的前缀和后缀的最长相等前后缀长度
下面我们从一个具体的例子来求解以上概念
按照规则一个个求前后缀即可，这里有一个小坑就是后缀是从往前的，所以是ba bab...
那么上面的部分匹配值表中某个字符不匹配时子串需要向后移动的位数计算公式如下
移动位数=已匹配的字符数-对应字符的部分匹配值
切记，此处查找的是最后一个匹配字符即下图b的部分匹配值
方法如下图所示，其余字符不匹配方法相同，直至字符串匹配成功或匹配失败为止
这里写错了 应该是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]]
如果递归一次后仍然相等则继续递归，直至不等即可
创作不易 觉得有帮助请点赞关注收藏~~~
