如何更好地舆解和掌握 KMP 算法?
如何更好地舆解和掌握 KMP 算法 我之前写过一篇 KMP 的文章，被读者这样评论为了保护读者隐私，所以都对其打上了马赛克，还被一些前辈称之为全网最细的 KMP 讲解，因为写的实在太用心了，我们一起往下看吧，如果觉得还不错的话，麻烦各位给我点个赞呀。
另外给大家推荐一下，我的面试网站，该网站对常考题目进行分类总结，对每个题解配备了 gif 图模拟，而且算法题还配有多个解题方法，让你快速拥有自己的刷题节奏和思路
网站首页 | 程序厨我们这里主要介绍三种算法，BF,BM,KMP 一点一点把 KMP 给吃的透透的！我们一起往下看吧
皇上生辰之际，举国同庆，袁记菜馆作为天下第一饭店，所以被选为这次庆典的菜品供应方，这次庆典对于袁记菜馆是一项前所未有的挑战，毕竟是第一次给皇上庆祝生辰，稍有不慎就是掉脑袋的大罪，整个袁记菜馆内都在紧张的布置着。此时突然有一个店小二慌慌张张跑到袁厨面前汇报，到底发生了什么事，让店小二如此慌张呢？
袁记菜馆内
店小二：不好了不好了，掌柜的，出大事了。
袁厨：发生什么事了，慢慢说，如此慌张，成何体统。（开店开久了，架子出来了哈）
店小二：皇上按照咱们菜单点了 666 道菜，但是咱们做西湖醋鱼的师傅请假回家结婚了，不知道皇上有没有点这道菜，如果点了这道菜，咱们做不出来，那咱们店可就完了啊。
（袁厨听了之后，吓得一屁股坐地上了，缓了半天说道）
袁厨：别说那么多了，快给我找找皇上点的菜里面，有没有这道菜！
找了很久，并且核对了很多遍，最后确认皇上没有点这道菜。菜馆内的人都松了一口气
通过上面的一个例子，让我们简单了解了字符串匹配。
字符串匹配：设 S 和 T 是给定的两个串，在主串 S 中找到模式串 T 的过程称为字符串匹配，如果在主串 S 中找到 模式串 T ，则称匹配成功，函数返回 T 在 S 中首次出现的位置，否则匹配不成功，返回-1。
例：
在上图中，我们试图找到模式 T = baab,在主串 S = abcabaabcabac 中第一次出现的位置，即为红色阴影部分， T 第一次在 S 中出现的位置下标为 4 （ 字符串的首位下标是 0 ），所以返回 4。如果模式串 T 没有在主串 S 中出现，则返回 -1。
解决上面问题的算法我们称之为字符串匹配算法，今天我们来介绍三种字符串匹配算法，大家记得打卡呀，说不准面试的时候就问到啦。
BF算法（Brute Force）
这个算法很容易理解，就是我们将模式串和主串进行比较，一致时则继续比较下一字符，直到比较完整个模式串。不一致时则将模式串后移一位，重新从模式串的首位开始对比，重复刚才的步骤下面我们看下这个方法的动图解析，看完肯定一下就能搞懂啦。
通过上面的代码是不是一下就将这个算法搞懂啦，下面我们用这个算法来解决下面这个经典题目吧。
leetcdoe 28. 实现 strStr()
题目描述
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回-1。
示例 1:
输入: haystack = "hello", needle = "ll" 输出: 2
示例 2:
输入: haystack = "aaaaa", needle = "bba" 输出: -1
题目解析
其实这个题目很容易理解，但是我们需要注意的是一下几点，比如我们的模式串为 0 时，应该返回什么，我们的模式串长度大于主串长度时，应该返回什么，也是我们需要注意的地方。下面我们来看一下题目代码吧。
题目代码
class Solution {
public int strStr(String haystack, String needle) {
int haylen = haystack.length();
int needlen = needle.length();
//特殊情况
if (haylen < needlen) {
return -1;
}
if (needlen == 0) {
return 0;
}
//主串
for (int i = 0; i < haylen - needlen + 1; ++i) {
int j;
//模式串
for (j = 0; j < needlen; j++) {
//不符合的情况，直接跳出，主串指针后移一位
if (haystack.charAt(i+j) != needle.charAt(j)) {
break;
}
}
//匹配成功
if (j == needlen) {
return i;
}
}
return -1;
}
}我们看一下BF算法的另一种算法（显示回退），其实原理一样，就是对代码进行了一下修改，只要是看完咱们的动图，这个也能够一下就能看懂，大家可以结合下面代码中的注释和动图进行理解。
class Solution {
public int strStr(String haystack, String needle) {
//i代表主串指针，j模式串
int i,j;
//主串长度和模式串长度
int halen = haystack.length();
int nelen = needle.length();
//循环条件，这里只有 i 增长
for (i = 0 , j = 0; i < halen && j < nelen; ++i) {
//相同时，则移动 j 指针
if (haystack.charAt(i) == needle.charAt(j)) {
++j;
} else {
//不匹配时，将 j 重新指向模式串的头部，将 i 本次匹配的开始位置的下一字符
i -= j;
j = 0;
}
}
//查询成功时返回索引，查询失败时返回 -1；
int renum = j == nelen ? i - nelen : -1;
return renum;
}
}BM算法(Boyer-Moore)
我们刚才说过了 BF 算法，但是 BF 算法是有缺陷的，比如我们下面这种情况
如上图所示，如果我们利用 BF 算法，遇到不匹配字符时，每次右移一位模式串，再重新从头进行匹配，我们观察一下，我们的模式串 abcdex 中每个字符都不一样，但是我们第一次进行字符串匹配时，abcde 都匹配成功，到 x 时失败，又因为模式串每位都不相同，所以我们不需要再每次右移一位，再重新比较，我们可以直接跳过某些步骤。如下图
我们可以跳过其中某些步骤，直接到下面这个步骤。那我们是依据什么原则呢？
坏字符规则
我们之前的 BF 算法是从前往后进行比较 ，BM 算法是从后往前进行比较，我们来看一下具体过程，我们还是利用上面的例子。
BM 算法是从后往前进行比较，此时我们发现比较的第一个字符就不匹配，我们将主串这个字符称之为坏字符，也就是 f ,我们发现坏字符之后，模式串 T 中查找是否含有该字符（f），我们发现并不存在 f，此时我们只需将模式串右移到坏字符的后面一位即可。如下图
那我们在模式串中找到坏字符该怎么办呢？
此时我们的坏字符为 f ,我们在模式串中，查找发现含有坏字符 f,我们则需要移动模式串 T ,将模式串中的 f 和坏字符对齐。见下图。
然后我们继续从右往左进行比较，发现 d 为坏字符，则需要将模式串中的 d 和坏字符对齐。
那么我们在来思考一下这种情况，那就是模式串中含有多个坏字符怎么办呢？
那么我们为什么要让最靠右的对应元素与坏字符匹配呢？如果上面的例子我们没有按照这条规则看下会产生什么问题。
如果没有按照我们上述规则，则会漏掉我们的真正匹配。我们的主串中是含有 babac 的，但是却没有匹配成功，所以应该遵守最靠右的对应字符与坏字符相对的规则。
我们上面一共介绍了三种移动情况，分别是下方的模式串中没有发现与坏字符对应的字符，发现一个对应字符，发现两个。这三种情况我们分别移动不同的位数，那我们是根据依据什么来决定移动位数的呢？下面我们给图中的字符加上下标。见下图
下面我们来考虑一下这种情况。
此时这种情况肯定是不行的，不往右移动，甚至还有可能左移，那么我们有没有什么办法解决这个问题呢？继续往下看吧。
好后缀规则
好后缀其实也很容易理解，我们之前说过 BM 算法是从右往左进行比较，下面我们来看下面这个例子。
这里如果我们按照坏字符进行移动是不合理的，这时我们可以使用好后缀规则，那么什么是好后缀呢？
BM 算法是从右往左进行比较，发现坏字符的时候此时 cac已经匹配成功，在红色阴影处发现坏字符。此时已经匹配成功的cac 则为我们的好后缀，此时我们拿它在模式串中查找，如果找到了另一个和好后缀相匹配的串，那我们就将另一个和好后缀相匹配的串 ，滑到和好后缀对齐的位置。
是不是感觉有点拗口，没关系，我们看下图，红色代表坏字符，绿色代表好后缀
上面那种情况搞懂了，但是我们思考一下下面这种情况
上面我们说到了，如果在模式串的头部没有发现好后缀，发现好后缀的子串也可以。但是为什么要强调这个头部呢？
我们下面来看一下这种情况
但是当我们在头部发现好后缀的子串时，是什么情况呢？
下面我们通过动图来看一下某一例子的具体的执行过程
说到这里，坏字符和好后缀规则就算说完了，坏字符很容易理解，我们对好后缀总结一下
1.如果模式串含有好后缀，无论是中间还是头部可以按照规则进行移动。如果好后缀在模式串中出现多次，则以最右侧的好后缀为基准。
2.如果模式串头部含有好后缀子串则可以按照规则进行移动，中间部分含有好后缀子串则不可以。
3.如果在模式串尾部就出现不匹配的情况，即不存在好后缀时，则根据坏字符进行移动，这里有的文章没有提到，是个需要特别注意的地方，我是在这个论文里找到答案的，感兴趣的同学可以看下。
Boyer R S，Moore J S. A fast string searching algorithm［J］. Communications of the ACM，1977，10： 762-772.
之前我们刚开始说坏字符的时候，是不是有可能会出现负值的情况，即往左移动的情况，所以我们为了解决这个问题，我们可以分别计算好后缀和坏字符往后滑动的位数（好后缀不为 0 的情况），然后取两个数中最大的，作为模式串往后滑动的位数。
这破图画起来是真费劲啊。下面我们来看一下算法代码，代码有点长，我都标上了注释也在网站上 AC 了，如果各位感兴趣可以看一下，不感兴趣理解坏字符和好后缀规则即可。可以直接跳到 KMP 部分
class Solution {
public int strStr(String haystack, String needle) {
char[] hay = haystack.toCharArray();
char[] need = needle.toCharArray();
int haylen = haystack.length();
int needlen = need.length;
return bm(hay,haylen,need,needlen);
}
//用来求坏字符情况下移动位数
private static void badChar(char[] b, int m, int[] bc) {
//初始化
for (int i = 0; i < 256; ++i) {
bc = -1;
}
//m 代表模式串的长度，如果有两个 a,则后面那个会覆盖前面那个
for (int i = 0; i < m; ++i) {
int ascii = (int)b;
bc = i;//下标
}
}
//用来求好后缀条件下的移动位数
private static void goodSuffix (char[] b, int m, int[] suffix,boolean[] prefix) {
//初始化
for (int i = 0; i < m; ++i) {
suffix = -1;
prefix = false;
}
for (int i = 0; i < m - 1; ++i) {
int j = i;
int k = 0;
while (j >= 0 && b == b) {
--j;
++k;
suffix = j + 1;
}
if (j == -1) prefix = true;
}
}
public static int bm (char[] a, int n, char[] b, int m) {
int[] bc = new int;//创建一个数组用来保存最右边字符的下标
badChar(b,m,bc);
//用来保存各种长度好后缀的最右位置的数组
int[] suffix_index = new int;
//判断是否是头部，如果是头部则true
boolean[] ispre = new boolean;
goodSuffix(b,m,suffix_index,ispre);
int i = 0;//第一个匹配字符
//注意结束条件
while (i <= n-m) {
int j;
//从后往前匹配，匹配失败，找到坏字符
for (j = m - 1; j >= 0; --j) {
if (a != b) break;
}
//模式串遍历完毕，匹配成功
if (j < 0) {
return i;
}
//下面为匹配失败时，如何处理
//求出坏字符规则下移动的位数，就是我们坏字符下标减最右边的下标
int x = j - bc[(int)a];
int y = 0;
//好后缀情况，求出好后缀情况下的移动位数,如果不含有好后缀的话，则按照坏字符来
if (y < m-1 && m - 1 - j > 0) {
y = move(j, m, suffix_index,ispre);
}
//移动
i = i + Math.max(x,y);
}
return -1;
}
// j代表坏字符的下标
private static int move (int j, int m, int[] suffix_index, boolean[] ispre) {
//好后缀长度
int k = m - 1 - j;
//如果含有长度为 k 的好后缀，返回移动位数，
if (suffix_index != -1) return j - suffix_index + 1;
//找头部为好后缀子串的最大长度，从长度最大的子串开始
for (int r = j + 2; r <= m-1; ++r) {
//如果是头部
if (ispre == true) {
return r;
}
}
//如果没有发现好后缀匹配的串，或者头部为好后缀子串，则移动到 m 位，也就是匹配串的长度
return m;
}
}我们来理解一下我们代码中用到的两个数组，因为两个规则的移动位数，只与模式串有关，与主串无关，所以我们可以提前求出每种情况的移动情况，保存到数组中。
KMP算法（Knuth-Morris-Pratt）
我们刚才讲了 BM 算法，虽然不是特别容易理解，但是如果你用心看的话肯定可以看懂的，我们再来看一个新的算法，这个算法是考研时必考的算法。实际上 BM 和 KMP 算法的本质是一样的，你理解了 BM 再来理解 KMP 那就是分分钟的事啦。
我们先来看一个实例
为了让读者更容易理解，我们将指针移动改成了模式串移动，两者相对与主串的移动是一致的，重新比较时都是从指针位置继续比较。
通过上面的实例是不是很快就能理解 KMP 算法的思想了，但是 KMP 的难点不是在这里，不过多思考，认真看理解起来也是很轻松的。
在上面的例子中我们提到了一个名词，最长公共前后缀，这个是什么意思呢？下面我们通过一个较简单的例子进行描述。
此时我们在红色阴影处匹配失败，绿色为匹配成功部分，则我们观察匹配成功的部分。
我们来看一下匹配成功部分的所有前缀
我们的最长公共前后缀如下图，则我们需要这样移动
好啦，看完上面的图，KMP的核心原理已经基本搞定了，但是我们现在的问题是，我们应该怎么才能知道他的最长公共前后缀的长度是多少呢？怎么知道移动多少位呢？
刚才我们在 BM 中说到，我们移动位数跟主串无关，只跟模式串有关，跟我们的 bc,suffix,prefix 数组的值有关，我们通过这些数组就可以知道我们每次移动多少位啦，其实 KMP 也有一个数组，这个数组叫做 next 数组，那么这个 next 数组存的是什么呢？
next 数组存的咱们最长公共前后缀中，前缀的结尾字符下标。是不是感觉有点别扭，我们通过一个例子进行说明。
我们知道 next 数组之后，我们的 KMP 算法实现起来就很容易啦，另外我们看一下 next 数组到底是干什么用的。
剩下的就不用说啦，完全一致啦，咱们将上面这个例子，翻译成和咱们开头对应的动画大家看一下。
下面我们看一下代码，标有详细注释，大家认真看呀。
注：很多教科书的 next 数组表示方式不一致，理解即可
class Solution {
public int strStr(String haystack, String needle) {
//两种特殊情况
if (needle.length() == 0) {
return 0;
}
if (haystack.length() == 0) {
return -1;
}
// char 数组
char[] hasyarr = haystack.toCharArray();
char[] nearr = needle.toCharArray();
//长度
int halen = hasyarr.length;
int nelen = nearr.length;
//返回下标
return kmp(hasyarr,halen,nearr,nelen);
}
public int kmp (char[] hasyarr, int halen, char[] nearr, int nelen) {
//获取next 数组
int[] next = next(nearr,nelen);
int j = 0;
for (int i = 0; i < halen; ++i) {
//发现不匹配的字符，然后根据 next 数组移动指针，移动到最大公共前后缀的，
//前缀的后一位,和咱们移动模式串的含义相同
while (j > 0 && hasyarr != nearr) {
j = next + 1;
//超出长度时，可以直接返回不存在
if (nelen - j + i > halen) {
return -1;
}
}
//如果相同就将指针同时后移一下，比较下个字符
if (hasyarr == nearr) {
++j;
}
//遍历完整个模式串，返回模式串的起点下标
if (j == nelen) {
return i - nelen + 1;
}
}
return -1;
}
//这一块比较难懂，不想看的同学可以忽略，了解大致含义即可，或者自己调试一下，看看运行情况
//我会每一步都写上注释
publicint[] next (char[] needle,int len) {
//定义 next 数组
int[] next = new int;
// 初始化
next = -1;
int k = -1;
for (int i = 1; i < len; ++i) {
//我们此时知道了 的最长前后缀，但是k+1的指向的值和i不相同时，我们则需要回溯
//因为 next就时用来记录子串的最长公共前后缀的尾坐标（即长度）
//就要找 k+1前一个元素在next数组里的值,即next
while (k != -1 && needle != needle) {
k = next;
}
// 相同情况，就是 k的下一位，和 i 相同时，此时我们已经知道 的最长前后缀
//然后 k - 1 又和 i 相同，最长前后缀加1，即可
if (needle == needle) {
++k;
}
next = k;
}
return next;
}
}好啦，大家看到这里就懂个大概啦，大家有哪里不了解的可以私信我一起讨论，如果觉得我写的很用心的话，对大家有一丢丢帮助的话，那就行大家给我点个赞吧，感谢各位支持。
另外大家可以看下这个 Github 仓库，对新手比较友好。
chefyuan/algorithm-base KMP算法是一种字符串匹配算法，可以在O(n+m) 的时间复杂度内实现两个字符串的匹配。本文将引导您学习KMP算法，阅读大约需要30分钟。
字符串匹配问题
所谓字符串匹配，是这样一种问题：“字符串 P 是否为字符串 S 的子串？如果是，它出现在 S 的哪些位置？” 其中 S 称为主串；P 称为模式串。下面的图片展示了一个例子。
主串是莎翁那句著名的 “to be or not to be”，这里删去了空格。“no” 这个模式串的匹配结果是“出现了一次，从S开始”；“ob”这个模式串的匹配结果是“出现了两次，分别从s、s开始”。按惯例，主串和模式串都以0开始编号。
字符串匹配是一个非常频繁的任务。例如，今有一份名单，你急切地想知道自己在不在名单上；又如，假设你拿到了一份文献，你希望快速地找到某个关键字（keyword）所在的章节……凡此种种，不胜枚举。
我们先从最朴素的Brute-Force算法开始讲起。
Brute-Force
顾名思义，Brute-Force是一个纯暴力算法。说句题外话，我怀疑，“暴力”一词在算法领域表示“穷举、极低效率的实现”，可能就是源于这个英文词。
首先，我们应该如何实现两个字符串 A,B 的比较？所谓字符串比较，就是问“两个字符串是否相等”。最朴素的思想，就是从前往后逐字符比较，一旦遇到不相同的字符，就返回False；如果两个字符串都结束了，仍然没有出现不对应的字符，则返回True。实现如下：
既然我们可以知道“两个字符串是否相等”，那么最朴素的字符串匹配算法 Brute-Force 就呼之欲出了——
[*]枚举 i = 0, 1, 2 ... , len(S)-len(P)
[*]将 S 与 P 作比较。如果一致，则找到了一个匹配。
现在我们来模拟 Brute-Force 算法，对主串 “AAAAAABC” 和模式串 “AAAB” 做匹配：
这是一个清晰明了的算法，实现也极其简单。下面给出Python和C++的实现：
我们成功实现了 Brute-Force 算法。现在，我们需要对它的时间复杂度做一点讨论。按照惯例，记 n = |S| 为串 S 的长度，m = |P| 为串 P 的长度。
考虑“字符串比较”这个小任务的复杂度。最坏情况发生在：两个字符串唯一的差别在最后一个字符。这种情况下，字符串比较必须走完整个字符串，才能给出结果，因此复杂度是 O(len) 的。
由此，不难想到 Brute-Force 算法所面对的最坏情况：主串形如“AAAAAAAAAAA...B”，而模式串形如“AAAAA...B”。每次字符串比较都需要付出 |P| 次字符比较的代价，总共需要比较 |S| - |P| + 1次，因此总时间复杂度是https://www.zhihu.com/equation?tex=O%28%7CP%7C%5Ccdot+%28%7CS%7C+-+%7CP%7C+%2B+1%29+%29 . 考虑到主串一般比模式串长很多，故 Brute-Force 的复杂度是 https://www.zhihu.com/equation?tex=O%28%7CP%7C+%5Ccdot+%7CS%7C%29 ，也就是 O(nm)的。这太慢了！
Brute-Force的改进思路
经过刚刚的分析，您已经看到，Brute-Force 慢得像爬一样。它最坏的情况如下图所示：
我们很难降低字符串比较的复杂度（因为比较两个字符串，真的只能逐个比较字符）。因此，我们考虑降低比较的趟数。如果比较的趟数能降到足够低，那么总的复杂度也将会下降很多。 要优化一个算法，首先要回答的问题是“我手上有什么信息？” 我们手上的信息是否足够、是否有效，决定了我们能把算法优化到何种程度。请记住：尽可能利用残余的信息，是KMP算法的思想所在。
在 Brute-Force 中，如果从 S 开始的那一趟比较失败了，算法会直接开始尝试从 S 开始比较。这种行为，属于典型的“没有从之前的错误中学到东西”。我们应当注意到，一次失败的匹配，会给我们提供宝贵的信息——如果 S 与 P 的匹配是在第 r 个位置失败的，那么从 S 开始的 (r-1) 个连续字符，一定与 P 的前 (r-1) 个字符一模一样！
需要实现的任务是“字符串匹配”，而每一次失败都会给我们换来一些信息——能告诉我们，主串的某一个子串等于模式串的某一个前缀。但是这又有什么用呢？
跳过不可能成功的字符串比较
有些趟字符串比较是有可能会成功的；有些则毫无可能。我们刚刚提到过，优化 Brute-Force 的路线是“尽量减少比较的趟数”，而如果我们跳过那些绝不可能成功的字符串比较，则可以希望复杂度降低到能接受的范围。
那么，哪些字符串比较是不可能成功的？来看一个例子。已知信息如下：
[*]模式串 P = &#34;abcabd&#34;.
[*]和主串从S开始匹配时，在 P 处失配。
首先，利用上一节的结论。既然是在 P 失配的，那么说明 S 等于 P，即&#34;abcab&#34;. 现在我们来考虑：从 S、S、S 开始的匹配尝试，有没有可能成功？
从 S 开始肯定没办法成功，因为 S = P = &#39;b&#39;，和 P 并不相等。从 S 开始也是没戏的，因为 S = P = &#39;c&#39;，并不等于P. 但是从 S 开始是有可能成功的——至少按照已知的信息，我们推不出矛盾。
带着“跳过不可能成功的尝试”的思想，我们来看next数组。
next数组
next数组是对于模式串而言的。P 的 next 数组定义为：next 表示 P ~ P 这一个子串，使得 前k个字符恰等于后k个字符 的最大的k. 特别地，k不能取i+1（因为这个子串一共才 i+1 个字符，自己肯定与自己相等，就没有意义了）。
上图给出了一个例子。P=&#34;abcabd&#34;时，next=2，这是因为P ~ P 这个子串是&#34;abcab&#34;，前两个字符与后两个字符相等，因此next取2. 而next=0，是因为&#34;abcabd&#34;找不到前缀与后缀相同，因此只能取0.
如果把模式串视为一把标尺，在主串上移动，那么 Brute-Force 就是每次失配之后只右移一位；改进算法则是每次失配之后，移很多位，跳过那些不可能匹配成功的位置。但是该如何确定要移多少位呢？
在 S 尝试匹配，失配于 S <=> P 之后，我们直接把模式串往右移了两位，让 S 对准 P. 接着继续匹配，失配于 S <=> P, 接下来我们把 P 往右平移了三位，把 S 对准 P. 此后继续匹配直到成功。
我们应该如何移动这把标尺？很明显，如图中蓝色箭头所示，旧的后缀要与新的前缀一致（如果不一致，那就肯定没法匹配上了）！
回忆next数组的性质：P 到 P 这一段子串中，前next个字符与后next个字符一模一样。既然如此，如果失配在 P, 那么P~P这一段里面，前next个字符恰好和后next个字符相等——也就是说，我们可以拿长度为 next 的那一段前缀，来顶替当前后缀的位置，让匹配继续下去！
您可以验证一下上面的匹配例子：P失配后，把P]也就是P对准了主串刚刚失配的那一位；P失配后，把P]也就是P对准了主串刚刚失配的那一位。
如上图所示，绿色部分是成功匹配，失配于红色部分。深绿色手绘线条标出了相等的前缀和后缀，其长度为next[右端]. 由于手绘线条部分的字符是一样的，所以直接把前面那条移到后面那条的位置。因此说，next数组为我们如何移动标尺提供了依据。接下来，我们实现这个优化的算法。
利用next数组进行匹配
了解了利用next数组加速字符串匹配的原理，我们接下来代码实现之。分为两个部分：建立next数组、利用next数组进行匹配。
首先是建立next数组。我们暂且用最朴素的做法，以后再回来优化：
如上图代码所示，直接根据next数组的定义来建立next数组。不难发现它的复杂度是 https://www.zhihu.com/equation?tex=O%28m%5E2%29 的。
接下来，实现利用next数组加速字符串匹配。代码如下：
如何分析这个字符串匹配的复杂度呢？乍一看，pos值可能不停地变成next，代价会很高；但我们使用摊还分析，显然pos值一共顶多自增len(S)次，因此pos值减少的次数不会高于len(S)次。由此，复杂度是可以接受的，不难分析出整个匹配算法的时间复杂度：O(n+m).
快速求next数组
终于来到了我们最后一个问题——如何快速构建next数组。
首先说一句：快速构建next数组，是KMP算法的精髓所在，核心思想是“P自己与自己做匹配”。
为什么这样说呢？回顾next数组的完整定义：
[*]定义 “k-前缀” 为一个字符串的前 k 个字符； “k-后缀” 为一个字符串的后 k 个字符。k 必须小于字符串长度。
[*]next 定义为： P~P 这一段字符串，使得k-前缀恰等于k-后缀的最大的k.
这个定义中，不知不觉地就包含了一个匹配——前缀和后缀相等。接下来，我们考虑采用递推的方式求出next数组。如果next, next, ... next均已知，那么如何求出 next 呢？
来分情况讨论。首先，已经知道了 next（以下记为now），如果 P 与 P 一样，那最长相等前后缀的长度就可以扩展一位，很明显 next = now + 1. 图示如下。
刚刚解决了 P = P 的情况。那如果 P 与 P 不一样，又该怎么办？
如图。长度为 now 的子串 A 和子串 B 是 P~P 中最长的公共前后缀。可惜 A 右边的字符和 B 右边的那个字符不相等，next不能改成 now+1 了。因此，我们应该缩短这个now，把它改成小一点的值，再来试试 P 是否等于 P.
now该缩小到多少呢？显然，我们不想让now缩小太多。因此我们决定，在保持“P~P的now-前缀仍然等于now-后缀”的前提下，让这个新的now尽可能大一点。 P~P 的公共前后缀，前缀一定落在串A里面、后缀一定落在串B里面。换句话讲：接下来now应该改成：使得 A的k-前缀等于B的k-后缀 的最大的k.
您应该已经注意到了一个非常强的性质——串A和串B是相同的！B的后缀等于A的后缀！因此，使得A的k-前缀等于B的k-后缀的最大的k，其实就是串A的最长公共前后缀的长度 —— next！
来看上面的例子。当P与P不相等的时候，我们需要缩小now——把now变成next，直到P=P为止。P=P时，就可以直接向右扩展了。
代码实现如下：
应用摊还分析，不难证明构建next数组的时间复杂度是O(m)的。至此，我们以O(n+m)的时间复杂度，实现了构建next数组、利用next数组进行字符串匹配。
以上就是KMP算法。它于1977年被提出，全称 Knuth–Morris–Pratt 算法。让我们记住前辈们的名字：Donald Knuth(K), James H. Morris(M), Vaughan Pratt(P).
希望本文对你有帮助。 本文在我博客的url是 https://ruanx.pw/kmp/ , 以后可能会更新。
<hr/>
最后附上洛谷P3375 【模板】KMP字符串匹配的Python和Java版代码：
本文是介绍 什么是 BF算法、KMP算法、BM算法 三部曲之一。
KMP算法 内部涉及到的数学原理与知识太多，本文只会对 KMP算法 的运行过程、 部分匹配表 、next数组 进行介绍，如果理解了这三点再去阅读其它有关 KMP算法 的文章肯定能有个清晰的认识。
以下的文字描述请结合视频动画来阅读~
七分钟理解什么是 KMP算法
https://www.zhihu.com/video/1139913258361397248
定义
Knuth-Morris-Pratt 字符串查找算法，简称为 KMP算法，常用于在一个文本串 S 内查找一个模式串 P 的出现位置。
这个算法由 Donald Knuth、Vaughan Pratt、James H. Morris 三人于 1977 年联合发表，故取这 3 人的姓氏命名此算法。
是不是感觉 Donald Knuth 这个名字很眼熟？没错，在前面 这或许是讲解 Knuth 洗牌算法最好的文章 一文中也出现了他！
下面直接给出 KMP算法 的操作流程：
[*]假设现在文本串 S 匹配到 i 位置，模式串 P 匹配到 j 位置
[*]如果 j = -1，或者当前字符匹配成功（即 S == P ），都令 i++，j++，继续匹配下一个字符；
如果 j != -1，且当前字符匹配失败（即 S != P ），则令 i 不变，j = next。此举意味着失配时，模式串 P相对于文本串 S 向右移动了 j - next 位
[*]换言之，将模式串 P 失配位置的 next 数组的值对应的模式串 P 的索引位置移动到失配处
看不明白？直接看动画！
运行过程
以下图文本串 S 与模式串 P 为例：
首先，列出模式串 P 的所有子串：
aababaabaaabaababaabcabaabcaabaabcac
然后，求得每一个子串的所有前缀与后缀。
前缀 指除了最后一个字符以外，一个字符串的全部头部组合；后缀 指除了第一个字符以外，一个字符串的全部尾部组合。
以第五列为例进行演示。
前缀为
aababaaba
后缀为
babaAbbaab
因此，它的前缀后缀的公共元素的最大长度为 2。
求得原模式串 P 的子串对应的各个前缀后缀的公共元素的 最大长度表 下图。
根据最大长度表 去求 next 数组：next 数组相当于“最大长度值” 整体向右移动一位，然后初始值赋为-1。
好了，获取了 next 数组 后，KMP 算法 的操作就很清晰了。
将模式串 P 与文本串 S 的字母一个个进行匹配，当失配的时候，模式串向右移动。
怎么移动？
比如模式串的 b 与文本串的 c 失配了，找出失配处模式串的 next数组 里面对应的值，这里为 0，然后将索引为 0 的位置移动到失配处。
我的专栏：
和程序员小吴一起学算法推荐一本好看的算法书 有些算法，适合从它产生的动机，如何设计与解决问题这样正向地去介绍。但KMP算法真的不适合这样去学。最好的办法是先搞清楚它所用的数据结构是什么，再搞清楚怎么用，最后为什么的问题就会有恍然大悟的感觉。我试着从这个思路再介绍一下。大家只需要记住一点，PMT是什么东西。然后自己临时推这个算法也是能推出来的，完全不需要死记硬背。
KMP算法的核心，是一个被称为部分匹配表(Partial Match Table)的数组。我觉得理解KMP的最大障碍就是很多人在看了很多关于KMP的文章之后，仍然搞不懂PMT中的值代表了什么意思。这里我们抛开所有的枝枝蔓蔓，先来解释一下这个数据到底是什么。
对于字符串“abababca”，它的PMT如下表所示：
就像例子中所示的，如果待匹配的模式字符串有8个字符，那么PMT就会有8个值。
我先解释一下字符串的前缀和后缀。如果字符串A和B，存在A=BS，其中S是任意的非空字符串，那就称B为A的前缀。例如，”Harry”的前缀包括{”H”, ”Ha”, ”Har”, ”Harr”}，我们把所有前缀组成的集合，称为字符串的前缀集合。同样可以定义后缀A=SB， 其中S是任意的非空字符串，那就称B为A的后缀，例如，”Potter”的后缀包括{”otter”, ”tter”, ”ter”, ”er”, ”r”}，然后把所有后缀组成的集合，称为字符串的后缀集合。要注意的是，字符串本身并不是自己的后缀。
有了这个定义，就可以说明PMT中的值的意义了。PMT中的值是字符串的前缀集合与后缀集合的交集中最长元素的长度。例如，对于”aba”，它的前缀集合为{”a”, ”ab”}，后缀 集合为{”ba”, ”a”}。两个集合的交集为{”a”}，那么长度最长的元素就是字符串”a”了，长 度为1，所以对于”aba”而言，它在PMT表中对应的值就是1。再比如，对于字符串”ababa”，它的前缀集合为{”a”, ”ab”, ”aba”, ”abab”}，它的后缀集合为{”baba”, ”aba”, ”ba”, ”a”}， 两个集合的交集为{”a”, ”aba”}，其中最长的元素为”aba”，长度为3。
好了，解释清楚这个表是什么之后，我们再来看如何使用这个表来加速字符串的查找，以及这样用的道理是什么。如图 1.12 所示，要在主字符串&#34;ababababca&#34;中查找模式字符串&#34;abababca&#34;。如果在 j 处字符不匹配，那么由于前边所说的模式字符串 PMT 的性质，主字符串中 i 指针之前的 PMT 位就一定与模式字符串的第 0 位至第 PMT 位是相同的。这是因为主字符串在 i 位失配，也就意味着主字符串从 i−j 到 i 这一段是与模式字符串的 0 到 j 这一段是完全相同的。而我们上面也解释了，模式字符串从 0 到 j−1 ，在这个例子中就是”ababab”，其前缀集合与后缀集合的交集的最长元素为”abab”， 长度为4。所以就可以断言，主字符串中i指针之前的 4 位一定与模式字符串的第0位至第 4 位是相同的，即长度为 4 的后缀与前缀相同。这样一来，我们就可以将这些字符段的比较省略掉。具体的做法是，保持i指针不动，然后将j指针指向模式字符串的PMT位即可。
简言之，以图中的例子来说，在 i 处失配，那么主字符串和模式字符串的前边6位就是相同的。又因为模式字符串的前6位，它的前4位前缀和后4位后缀是相同的，所以我们推知主字符串i之前的4位和模式字符串开头的4位是相同的。就是图中的灰色部分。那这部分就不用再比较了。
有了上面的思路，我们就可以使用PMT加速字符串的查找了。我们看到如果是在 j 位 失配，那么影响 j 指针回溯的位置的其实是第 j −1 位的 PMT 值，所以为了编程的方便， 我们不直接使用PMT数组，而是将PMT数组向后偏移一位。我们把新得到的这个数组称为next数组。下面给出根据next数组进行字符串匹配加速的字符串匹配程序。其中要注意的一个技巧是，在把PMT进行向右偏移时，第0位的值，我们将其设成了-1，这只是为了编程的方便，并没有其他的意义。在本节的例子中，next数组如下表所示。
具体的程序如下所示：
int KMP(char * t, char * p)
{
int i = 0;
int j = 0;
while (i < (int)strlen(t) && j < (int)strlen(p))
{
if (j == -1 || t == p)
{
i++;
j++;
}
else
j = next;
}
if (j == strlen(p))
return i - j;
else
return -1;
}
好了，讲到这里，其实KMP算法的主体就已经讲解完了。你会发现，其实KMP算法的动机是很简单的，解决的方案也很简单。远没有很多教材和算法书里所讲的那么乱七八糟，只要搞明白了PMT的意义，其实整个算法都迎刃而解。
现在，我们再看一下如何编程快速求得next数组。其实，求next数组的过程完全可以看成字符串匹配的过程，即以模式字符串为主字符串，以模式字符串的前缀为目标字符串，一旦字符串匹配成功，那么当前的next值就是匹配成功的字符串的长度。
具体来说，就是从模式字符串的第一位(注意，不包括第0位)开始对自身进行匹配运算。 在任一位置，能匹配的最长长度就是当前位置的next值。如下图所示。
求next数组值的程序如下所示：
void getNext(char * p, int * next)
{
next = -1;
int i = 0, j = -1;
while (i < (int)strlen(p))
{
if (j == -1 || p == p)
{
++i;
++j;
next = j;
}
else
j = next;
}
}
至此，KMP算法就全部介绍完了。
=====================
在基础软件领域转了一圈，被人鼓动着能不能把最核心的知识总结下来。于是就上线了这个专栏：
编程高手必学的内存知识_内存_海纳_系统级程序员_系统开发_软件开发_操作系统_进程_CPU_硬件_修炼内功_垃圾回收_cache_链接_内存管理_内存模型_编译器-极客时间如果你喜欢底层软件开发，想研究底层知识，可以关注一下。 角色：
甲：abbaabbaaba
乙：abbaaba
乙对甲说：「帮忙找一下我在你的哪个位置。」
甲从头开始与乙一一比较，发现第 7 个字符不匹配。
要是在往常，甲会回退到自己的第 2 个字符，乙则回退到自己的开头，然后两人开始重新比较。这样的事情在字符串王国中每天都在上演：不匹配，回退，不匹配，回退，……
但总有一些妖艳字符串要花自己不少的时间。
上了年纪的甲想做出一些改变。于是乎定了个小目标：发生不匹配，自身不回退。
甲发现，若要成功与乙匹配，必须要匹配 7 个长度的字符。所以就算自己回退到第 2 个字符，在后续的匹配流程中，肯定还会重新匹配到自己的第 7 个字符上。
当在甲的某个字符 c 上发生不匹配时，甲即使回退，最终还是会重新匹配到字符 c 上。
那干脆不回退，岂不美哉！
甲不回退，乙必须回退地尽可能少，并且乙回退位置的前面那段已经和甲匹配，这样甲才能不用回退。
如何找到乙回退的位置？
「不匹配发生时，前面匹配的那一小段 abbaab 于我俩是相同的」，甲想，「这样的话，用 abbaab 的头部去匹配 abbaab 的尾部，最长的那段就是答案。」
abbaab 的头部有 a, ab, abb, abba, abbaa（不包含最后一个字符。下文称之为「真前缀」）
abbaab 的尾部有 b, ab, aab, baab, bbaab（不包含第一个字符。下文称之为「真后缀」）
这样最长匹配是 ab。也就是说甲不回退时，乙需要回退到第三个字符去和甲继续匹配。「要计算的内容只和乙有关」，甲想，「那就假设乙在其所有位置上都发生了不匹配，乙在和我匹配前把其所有位置的最长匹配都算出来（算个长度就行），生成一张表，之后我俩发生不匹配时直接查这张表就行。」
据此，甲总结出了一条规则并告诉了乙：
所有要与甲匹配的字符串（称之为模式串），必须先自身匹配：对每个子字符串 ，算出其「相匹配的真前缀与真后缀中，最长的字符串的长度」。
「小 case，我对自己还不了解吗」，乙眨了一下眼睛，「那我回退到第三个字符和你继续匹配吧~」
<hr/>新的规则很快传遍了字符串王国。现在来看看如何高效地计算这条规则。这里有个很好的例子：abababzabababa。
列个表手算一下：（最大匹配数为子字符串 的最长匹配的长度）
子字符串 a b a b a b z a b a b a b a
最大匹配数 0 0 1 2 3 4 0 1 2 3 4 5 6 ?一直算到 6 都很容易。在往下算之前，先回顾下我们所做的工作：
对子字符串 abababzababab 来说，
真前缀有 a, ab, aba, abab, ababa, ababab, abababz, ...
真后缀有 b, ab, bab, abab, babab, ababab, zababab, ...
所以子字符串 abababzababab 的真前缀和真后缀最大匹配了 6 个（ababab），那次大匹配了多少呢？
容易看出次大匹配了 4 个（abab），更仔细地观察可以发现，次大匹配必定在最大匹配 ababab 中，所以次大匹配数就是 ababab 的最大匹配数！
直接去查算出的表，可以得出该值为 4。
第三大的匹配数同理，它既然比 4 要小，那真前缀和真后缀也只能在 abab 中找，即 abab 的最大匹配数，查表可得该值为 2。
再往下就没有更短的匹配了。
回顾完毕，来计算 ? 的值：既然末尾字母不是 z，那么就不能直接 6+1=7 了，我们回退到次大匹配 abab，刚好 abab 之后的 a 与末尾的 a 匹配，所以 ? 处的最大匹配数为 5。
<hr/>上 Java 代码，它已经呼之欲出了：
// 构造模式串 pattern 的最大匹配数表
int[] calculateMaxMatchLengths(String pattern) {
int[] maxMatchLengths = new int;
int maxLength = 0;
for (int i = 1; i < pattern.length(); i++) {
while (maxLength > 0 && pattern.charAt(maxLength) != pattern.charAt(i)) {
maxLength = maxMatchLengths; // ①
}
if (pattern.charAt(maxLength) == pattern.charAt(i)) {
maxLength++; // ②
}
maxMatchLengths = maxLength;
}
return maxMatchLengths;
}有了代码后，容易证明它的复杂度是线性的（即运算时间与模式串 pattern 的长度是线性关系）：由 ② 可以看出 maxLength 在整个 for 循环中最多增加 pattern.length() - 1 次，所以让 maxLength 减少的 ① 在整个 for 循环中最多会执行 pattern.length() - 1 次，从而 calculateMaxMatchLengths 的复杂度是线性的。
KMP 匹配的过程和求最大匹配数的过程类似，从 count 值的增减容易看出它也是线性复杂度的：
// 在文本 text 中寻找模式串 pattern，返回所有匹配的位置开头
List<Integer> search(String text, String pattern) {
List<Integer> positions = new ArrayList<>();
int[] maxMatchLengths = calculateMaxMatchLengths(pattern);
int count = 0;
for (int i = 0; i < text.length(); i++) {
while (count > 0 && pattern.charAt(count) != text.charAt(i)) {
count = maxMatchLengths;
}
if (pattern.charAt(count) == text.charAt(i)) {
count++;
}
if (count == pattern.length()) {
positions.add(i - pattern.length() + 1);
count = maxMatchLengths;
}
}
return positions;
}
最后总结下这个算法：
[*]匹配失败时，总是能够让模式串回退到某个位置，使文本不用回退。
[*]在字符串比较时，模式串提供的信息越多，计算复杂度越低。（有兴趣的可以了解一下 Trie 树，这是文本提供的信息越多，计算复杂度越低的一个例子。）
页:
[1]