不懂KMP算法？一次性带你秒杀！

KMP算法由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。

---

---

前言

KMP算法在我看来是一种学起来比较困难但一学会之后就特别简明清晰的算法。
因为其本身的核心思想就并不是太难，所以在看本文的时候不要潜意识的认为算法很难，
尽量用简单的方式去思考，不懂的地方其实多模拟几次就懂了。

再一个就是本人是一个萌新初学者，在一些解释方面可能会出现偏差和错误，请见谅。
我会用我的方式来让读者更快的理解KMP。

---

问题类型

相信读者在看我的文章时已经或多或少的了解过一些其他的KMP讲解了。
其实这个算法就是为了解决字符串匹配问题，简单来说就是寻找一个字符串里是否包含另一个字符串并可以返回其起始位置，
也可以用来寻找一个字符串中包含几个相同的子字符串，例：

str1=zyzyzyz
str2=zyz

则str1中包含了三个str2,起始位置分别是0,2,4。

KMP其实还有非常多的变式应用，只不过我都不会 这里就不再赘述，请读者自行查阅资料了解。

废话不多说，进入算法讲解部分。

算法讲解

什么是KMP?

KMP就是是一种改进的字符串匹配算法。
我们都知道，普通的暴力是一位一位的挪动字符串并逐位比较，
这样的时间复杂度会达到 $O(nm)$，非常不利。

而KMP则是通过比较操作的简化来优化时间复杂度，不是一位一位的移动，
而是不后退的一段一段的移动，有读者想问：这不会出现遗漏的错误么？
这时候，就需要用到一个移动数组next，KMP算法的核心部分就是next数组的应用，使其时间复杂度大大降低，达到 $O(n+m)$

next数组

next数组的含义

首先要明白next数组是什么——
$next[i]$ 表示一个字符串前 $i$ 个字符的最长前缀和最长后缀相同的长度。
其中-1表示无最长前缀和最长后缀，0表示1,1表示2，以此类推。
还是不明白？
举个例子：

str=ababc;
next[1]=-1;  /none
next[2]=-1;  /none
next[3]=0;   /a 是最长前缀和最长后缀相同的字符串
next[4]=1;   /ab 是最长前缀和最长后缀相同的字符串
next[5]=-1;  /none

两个注意点：

1. “kkkk” 的最长前缀和最长后缀相同的长度是 3，最长前缀和最长后缀相同的字符串为"kkk"！
2. 在“aba”中，ab和ba 不能算作是最长前缀和最长后缀相同！

next数组的求法

知道了next数组的含义之后，就来看看传说中“很难”的求法。
暴力？肯定不行，这样就失去了KMP的意义。
其实，next数组的求法也是 $O(n+m)$.
下面我就用图加文字的方式解说next数组的求法。
以字符串"ababc"为例来演示：
$k$ 代表当前字符串最长前缀和最长后缀相同的长度为 $k$。
$i$ 代表当前字符串到了第 $i$ 位。

此时字符串“a”没有最长前缀和最长后缀相同，$next[0]=-1$;

这时字符串"ab"仍没有最长前缀和最长后缀相同，$next[1]=-1$;

(未完待续)

转载：https://blog.csdn.net/Jackma_mayichao/article/details/114732596