前言
1.算法学习，三分靠别人题解，七分靠自己理解。
2.前一阵有同学问过我，我也做过KMP的题，但是当时只是会板子，理解的并不是很深，所以直接把大佬题解给那个同学了。这次数据结构，理解比较好了，才敢自己写讲解。
最朴素的暴力时间复杂度O(n*m)
文本串 s 的长度为 n ，模式串 p 的长度为 m ，通过i指针访问 s 串每个位置的字符，通过 j 指针访问 p 串每个位置的字符。
最朴素的暴力就是，若 i 指向的字符与 j 指向的字符一样，那 i，j 一起后移；若不相等，i 回溯到开始与j相同的下一个位置，j 回溯到 p 串的开头。
i 指针遍历一遍 s 串，对于每一个不同的 i ，最差情况 j 遍历一遍 p 串，因此整个算法的时间复杂度 O(n*m)
因为存在 i 指针的回溯，所以时间复杂度其实比 O(n*m)要大。
如何降低时间复杂度？
还是上面的例子：
因为我们要找能匹配好的部分，但是，很显然，失配（绿框内）的次数太多造成了不必要的时间浪费，失配的步骤并不是我们期望的。
对于上图而言，我们最希望的匹配方式肯定是，在s串中的b与p串中的c匹配失败后（绿框中的第一步），直接跳到 s 串中的 a 与 p 串中的 a 匹配（绿框后一步），这就是我们优化灵感的来源。
KMP算法
时间复杂度不同的原因
暴力算法本质：i 指针回溯，j 指针回溯；
KMP算法本质：i 指针不回溯，j 指针回溯。
前缀和后缀的概念：
引入这两个概念是方便后面的理解。
（直接举例，方便理解）
对于abcde而言，
其前缀有：a/ab/abc/abcd；其后缀有：e/de/cde/bcde
前缀和后缀都不包含自身，即不包含abcde
KMP算法讲解
i 指针无需回溯，只要顺序遍历即可；j 指针在失配时，要进行回溯，那么我们用 next 数组存储 j 要回溯到哪，即next[j]=j要回溯到的位置
（先直接告诉你 next 数组的每个元素是多少，之后会对 next 数组进行讲解）
next[j] 表示对于 p 串中前 j-1 个字符而言，前缀与后缀相同的最大长度 +1。
还是以上面的 p 串为例：
先求 next[5]，也就是说此时 j=5 ，我们要求前 j-1 个字符（紫框）的前缀与后缀相同的最大长度 +1。
我们首先得确定前缀与后缀吧，前缀有三个，分别为a，ab，abc，后缀有三个，分别为a，ca，bca；
前缀与后缀相同的最长的字符串为a吧，因为ab!=ca,abc!=bca，只能是a==a了，所以前缀与后缀相同的最大长度为 1 ，那么再加个 1 ，就是 2 。因此，我们可以确定next[5]=2，其含义为当 j=5 失配时，j 要回溯到 next[j] = next[5] 的位置，即 j 变成 2 。
同理，再求 next[4]，其前三个字符的前缀与后缀相同的最大长度为 0 ，最后 +1 ，得到 next[4] = 1 。
以此类推，next[3] = 1 ，next[2] = 1 ，同时我们规定 next[1] = 0 。
最终得到：
用KMP算法匹配
我们现在知道每次失配之后j要回溯到的位置了，再尝试着匹配一遍上面的例子。
其中绿框部分是暴力算法存在，而KMP算法不存在的匹配过程，也就是KMP对于匹配过程的优化。
重点关注绿框前一步和后一步，这是绿框内步骤省略的原因。
为什么求个前缀与后缀相同的长度就行呢？
书上的证明（比较难理解，毕竟比较严谨，下面我通过图形不严谨地证明一下，主要是方便大家理解）：
我的证明：
上图：s 串的 i 与 p 串的 j 进行匹配（紫色部分），说明 s 串的红色部分一定和 p 串的红色部分匹配了，其中黑色部分表示可能存在字符。
上图：绿框所围部分与蓝框所围部分是 p 串前 j-1 个字符前后缀相同的最长子串，褐色是 s 串中与 p 串蓝色部分相同的部分，因为 s 串和 p 串的红色部分是一一对应的，自然，褐***域与蓝***域的字符也是一一对应的。又由于绿色框所表示的前缀与蓝色框表示的后缀相同，褐色框部分与绿色框部分也就相同，即 蓝色=绿色 并且 蓝色=褐色 => 褐色=绿色。这说明褐色部分与绿色部分也匹配啊，所以我们要让 j 指针回溯到绿框的后一个元素与 i 指向的元素比较就行了。
下图：回溯完成
KMP算法代码
理解了这个过程之后，代码写起来易如反掌。
//c++代码，初学者可忽略
bool Match(string s,string p){
int n=s.size(),m=p.size(),i=1,j=1;
s='.'+s;
p='.'+p;
while(i<=n && j<=m) {
if(j==0 || s[i]==p[j]) ++i,++j;
else j=next[j];
}
if(j>m) return true;
else return false;
}
//伪代码，数据结构学习者
Status KMP_Match(SString S,SString P){//S为主串，P为模式串
i=1;//从第一个字符开始匹配
j=1;//同上
while(i<=StrLength(S) && j<=StrLength(P)){//只有在i未到S串最后且j未到P串最后时才进行
if(j==0 || S[i]==P[j]) {++i;++j;}//匹配成功或者j指针到头了，i，j指针后移
else j=next[j];//回溯j指针
}
if(j>StrLength(P)) return Match_successed;//若j指针超过了P的长度，说明P串成功匹配
else Match_failed;//反之，未成功
}构建next数组
到现在，我们只是知道了 next 数组的值与前缀和后缀有关，也知道了如何使用 next 数组对 j 指针进行回溯，但是我们还不知道怎么构建 next 数组。
你只要看懂了KMP算法的过程，next 数组构建的过程肯定不在话下。
因为构建 next 数组的过程就是 P 串与 P 串通过KMP算法匹配的过程。
此话怎讲？
next数组构建讲解
在构建 next 数组的过程中，主串为 P 串，模式串也为 P 串，只不过，这两个串直接从头到尾匹配肯定是完全一样，所以，我们要错位匹配。还是以上面的 p 串为例， p：abcac。
对应匹配： （过程与KMP算法相同）
构建next数组的代码
//c++代码，初学者忽略
void CreateNext(string p){
Next[1]=0;//易漏！
int i=1,j=0,n=p.size();//j初始化为0
p='.'+p;
while(i<=n && j<=n){
if(j==0 || p[i]==p[j]){
++i,++j;
Next[i]=j;//对next数组赋值
}
else j=Next[j];
}
}
//伪代码，数据结构
void Create_Next(SString P,int next[]){
i=1;
next[1]=0;//易漏
j=0;//注意
while(i<=StrLength(P) && j<=StrLength(P){
if(j==0 || P[i]==P[j]){
++i;++j;
next[i]=j;//对next数组赋值
}
else j=next[j];
}
}小总结
next 数组的构建就是利用KMP算法错位匹配字符串 p ，同时对 next 数组进行赋值操作。
next数组构建的优化
引例
所有的东西我都帮你算好了。
接下来可以进行匹配了。
问题
问题出现了，红框内为 i 指向字符 c，j 指向字符 b，匹配不成功，要对 j 进行回溯，但是 j 回溯之后指向的还是字符 b（此 b 非前面那个 b ）依旧无法与 i 指向的字符 c 相匹配。
而我们的期望肯定是尽可能回溯到匹配的位置继续进行匹配，这显然违背我们的初衷，所以我们可以再从此处进行优化进一步降低时间复杂度。
分析原因与解决问题
问题出在不该出现 p[j] = p[ next[j] ]。
为什么呢？
理由是：当p[j] != s[i]时，下次匹配必然是p[ next [j]]跟s[i]匹配，如果p[j] = p[ next[j] ]，必然导致后一步匹配失败（因为p[j]已经跟s[i]失配，然后你还用跟p[j]等同的值p[next[j]]去跟s[i]匹配，很显然，必然失配），所以不能允许p[j] = p[ next[j] ]。如果出现了p[j] = p[ next[j] ]咋办呢？如果出现了，则需要再次回溯，即令next[j] = next[ next[j] ]。
图片说明：
构建next数组的优化代码
//c++，初学者忽略
void CreateNext(string p){
Next[1]=0;
int i=1,j=0,len=p.size();
p='.'+p;
while(i<=len){
if(j==0 || p[i]==p[j]){//通过i去更新next里面存储的位置
++i;++j;
if(p[i]==p[j]) Next[i]=Next[Next[i]];//此时next[i]=j，因此 <=> next[i]=next[j];
else Next[i]=j;
}
else j=Next[j];
}
}
//伪代码，数据结构
void Create_Next(SString P,int next[]){
i=1;
next[1]=0;
j=0;
while(i<=StrLength(P) && j<=StrLength(P)){
if(j==0 || P[i]==P[j]){
++i;++j;
if(P[i]!=P[j]) next[i]=j;
else next[i]=next[j];
}
else j=next[j];
}
}另附 KMP题目
https://www.luogu.com.cn/problem/P3375
https://ac.nowcoder.com/acm/contest/7412/G
https://www.acwing.com/problem/content/description/143/
https://www.luogu.com.cn/problem/P2375
参考文章
https://blog.csdn.net/weixin_45697774/article/details/106039012
https://www.cnblogs.com/cherryljr/p/6519748.html
https://www.zhihu.com/question/21923021
数据结构（C语言版）清华大学出版社
京公网安备 11010502036488号