数据结构与算法基础（王卓）（17）：KMP算法详解（精讲（最简单、直接、有效的思路方法，答案以及代码原理）

本文具体思路参考： （最后证明，该教材/网课实际上是最有效的） 

DS第四章【3】KMP1_哔哩哔哩_bilibili

---

中间走的一些弯路的教材： 

第06周05--第4章串、数组和广义表5-4.3串的操作--串的匹配算法2--KMP算法_哔哩哔哩_bilibili

课本

走弯路过程，详见

数据结构与算法基础（王卓）（16）：KMP算法（个人学习历程）

虽然里面学的过程用的很多的是生硬的笨方法，但是里面遇到的问题和踩的坑还是值得一看来更深理解KMP算法的

---

 PART 1：关于next [ j ]

PPT：P30 （根据DS第四章【3】KMP1_哔哩哔哩_bilibili）

---

需求：

返回子串和主串匹配时候的位置

---

思想：

把上面的主串（（也就是）箭头左边的（前面的）那一部分）当成箭头左边的子串的一个分身

注：比较到不匹配时，箭头（指针）指向不匹配的字符

他们之间公共的部分：

要么是完全对其时候的全部

要么是下面的子串移动到其（主串）公共后缀的位置的时候

其他上下两个串摆放的位置，都不可能产生我们想要的，公共的部分

其实分析这个问题的时候我们就已经不用去看主串的位置和情况了，因为其实我们已经知道：

在匹配不上的前面（箭头左边），子串和主串都是一样的，所以其实只要看子串就行了

所以我们只需要找出前面（箭头左边）的公共前后缀

然后往前（右）移动子串，让他的前缀移动到原来后缀的位置

就可以解决这个问题，往下比较了

---

核心：

直接把前缀移动到（移动）之前后缀所处的位置，跳过这中间所有的字符

---

好了，现在我们思路有了，接下来：

具体落实怎么移动：

移动目的：找到主串子串完全匹配的位置

如果发生的是主串和子串比较的字符匹配的情况，我觉得我们根本不用讨论

现在比较的这一位匹配，那就比较下一位

如果一路匹配下去一直都是能匹配的上的话，那就返回结果：

子串放在第一格，可以和主串匹配上

就行了

所以我们需要讨论解决的，是当每一位发生了不匹配的操作时，我们怎么相对应的处理

另外，我们这里不仅要知道下一步该具体怎么移动，还需要思考：

如何用指针实现进一步的比较（所有的探究、思路，都是为了写出程序服务）

现在，我们知道了当每一步（每一种）情况，我们应该怎么进行操作

根据上图，我们就得到了下一步如何操作（把子串的指针移动到哪个位置的操作）的

公式：

字符串从位序 1 开始存储时：

PPT（网课）上的归纳公式

字符串从位序 0 开始存储时：

书上的公式

---

以上都是怎么进行移动的公式、思路、理论，接下来我们是要写代码的：

先不写KMP算法代码，我们先写求：每一位匹配不上情况的next（把子串的指针移动到哪个位序）

当我们一个一个排（匹配）下去，显然，当我们比较（两个字符）的时候：

1. 这个字符前面的所有字符都应该是匹配的，如果不匹配，我们就移动子串的指针位置，重新从头开始比较
2. 这个字符前面的所有字符的 next 数组的信息，我们都是可以知道的

所以

现在，我们每往下走一步面临的问题就是：

主串和子串比较的字符匹配【if（1）】，讨论无意义

		if (k == -1 || T.ch[k] == T.ch[j]){j++;k++;next[j] = k;}

所以讨论不匹配时【if（0）】，怎么处理：我们面临的情况：

再次强调：

 我们要把思路转变一下

不是说我们求的是next【j】

而是我们求的是next【j+1】

我们需要的是从过去推出未来，而不是说

未来是什么我不知道，然后我再去猜过去式这种情况还是那种情况

那种的情况(不等)又只知道一半

只知道最后面一个字符不匹配，在前面的就不知道了

这样研究的话，那还不如具象化的研究

不要让自己走向未知的方向。走进越来越未知的方向

从已知走向未知，让未知走向已知

---

把上面的这个模式串（子串）分身【位序 j - k 到 k - 1 】看成主串

把下面的这个模式串（子串）分身【位序 0 到 k - 1 】看成子串

于是该问题转化为：

主串与模式串最后一个字符不匹配

然后同样的，比较；比较什么：

子串里有没有公共前后缀

确定后面该移到哪个位置

特别注意：

不要遗漏已知条件：（这个条件和之前主串子串匹配同样类似/相似）

在我们这个不匹配的字符前面，所有的字符全部都匹配

现在我们回到解决问题的

核心：子串（模式串）该移到哪个位置

---

kmp算法：

同样的，找到这里子串【0到k】前面的公共前后缀

然后把前缀移动到后缀的位置，看看新的前缀后面的字符能不能和第 j 位匹配得上

操作上面的图已经写了：

子串指针移动到【k + 1】位序

		elsek = next[k];

---

如果我们一定想用bf算法：（证明我们真的熟练掌握了这种思想）

如果我们用bf算法，也就是说一格一格往右边移

主串位置不变，子串一格一格往右边移动，一次一次比较

直到匹配成功到 前缀后缀一样 乃至子串和主串一样为止

所以我们要进行的操作就是：

主串指针不变，子串指针不断指向前面一个字符，下一次比较

实际操作就是：k--：

		elsek--;

---

再次强调：

匹配“下一位字符”之前，我们不用担心

他（这个“下一位字符”）和主串前面部分的字符能否匹配得上

这个问题的

即使这个“下一位字符”不匹配，在我们这个不匹配的字符前面，所有的字符全部都匹配

---

疑问：

为什么不从中间开始匹配？

如果中间有和后缀一样的，但是开头没有呢？

我们要求必须从开头开始算前缀是不是容易漏掉一些可能的正确答案呢？

答案：

如果中间有，但是开头不行，那最后子串中间的字符是匹配了，但是中间的 前面的那部分字符终究还是不匹配，那迟早要完蛋，终究是失败的 

---

另外

为了强调和体现我们“求的是next【j+1】”的思想和精神，我们不妨把【if（1）】处的代码更新为：（虽然我后面最后的答案里面不是这么写的）

		if (k == -1 || T.ch[k] == T.ch[j]){next[j + 1] = k + 1;j++;k++;}

---

答案：

#include<iostream>
using namespace std;
#include<stdlib.h>//存放exit
#include<math.h>//OVERFLOW,exittypedef int Status;
#define MAXLEN 255struct SString//Sequence String
{char ch[MAXLEN + 1]; //存储串的一维数组int length; //串的当前长度长度
};void Get_next(SString T, int *next)
//给你一个子串T，教你逐个算出每个位序对应的next[]
{int j = 0,//从头开始算起k = -1;next[0] = -1;//根据公式while (j <= T.length - 1)//因为位序从0（而非1）开始{if (k == -1 || T.ch[k] == T.ch[j]){j++;k++;next[j] = k;}elsek = next[k];}
}int Index_KMP(SString S, SString T, int pos)
{int next[MAXLEN];Get_next(T, next);int i = pos, j = 1;while (i <= S.length && j <= T.length){if (S.ch[i] == T.ch[j]){++i; ++j;}//主串和子串依次匹配下一个字符elsej = next[j];}if (j > T.length)return i - T.length; //匹配成功elsereturn 0;
}int main()
{}