KMP算法是一种改进的字符串匹配算法，由 D.E.Knuth，J.H.Morris 和 V.R.Pratt 提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称 KMP 算法）。
KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个 next 数组实现的，数组本身包含了模式串的局部匹配信息。KMP 算法的时间复杂度 O(m+n) 。
与 BF 算法进行区别：KMP 和 BF 唯一不一样的地方在，我主串的 i 并不会回退，并且 j 也不会直接移动到 0 号下标，而是移动到特定的位置，而这个特定的位置就是该位置上 next 数组中存储子串要移动位置的下标！
2、next数组的引入
首先举例，为什么主串位置 i 不回退❓❓❓
我们需要一个特定的例子来说明这个问题：
另一个问题：子串 j 该如何回退？同样的，先来看一个例子：
Next数组的引入：
简单理解就是：来保存子串某个位置匹配失败后，回退的位置。
不同的 j 来对应一个回退值， 这个回退值就是你将来要移动的 j 要移动的位置。
💥💥💥回退值是这样求的 ：
- 在子串中找到匹配成功部分的两个相等的真子串（不包含本身），一个以下标
0字符开始，另一个以j-1下标字符结尾。 - 规定 next[0] = -1；next[1] = 0；在这里，我们以下标来开始，而说到的第几个第几个是从 1 开始；
看到这里，你可能还是懵的，对于回退值是如何求的还是不理解，我们通过两个练习来求回退值，你就知道是怎么求的了
练习 1： 举例对于”ababcabcdabcde”， 求其的 next 数组？
练习 2： 再对”abcabcabcabcdabcde”,求其的 next 数组？
接下来的问题就是：已知 next[i] = k，怎么求 next[i+1]❓❓❓
如果我们能够通过 next[i] 的值,通过一系列转换得到 next[i+1] 的值，那么我们就能够实现这部分。
首先假设： next[i] = k 成立，那么就有这个式子成立：P[0]……P[k-1] = P[x]……P[i-1] 看个图就知道什么意思了：
根据图片内公式转化，此时得到： P[0]……P[k-1] = P[i-k]……P[i-1]。
到这一步，我们再假设如果 P[k] = P[i]，我们就可以得到 P[0]…P[k] = P[i-k]…P[i]。（等式两边尾部分别添上了 P[k] 和 P[i]）
💥💥💥此时我们就能达到公式： next[i+1] = k+1。
为什么❓❓❓
那如果是 P[k] != P[i] 呢，此时 next[i+1] 是多少 ❓❓❓
此时的做法就是让 k = next[k] 不断的回退，直到找到了 P[i] == p[k] 或者 k出界 的情况：
至此，KMP的算法的思想到这里大部分结束。下面，我们通过代码来进行实现：
3、KMP代码实现
#include <iostream>
#include <string>
#include <vector>
using namespace std;
/*
字符串匹配算法
1、BF算法(效率低）×
2、KMP算法 ✔
str: 代表主串
sub：代表子串
next：代表的就是next数组
KMP函数要求：返回匹配位置的下标，若不匹配则返回-1
*/
void getNext(const string& sub, vector<int>& next, int n)
{
// 先将固定的值赋值
next[0] = -1;
// 这里两个下标是与解析对应起来的
int i = 1;
int k = 0;
while(i < n - 1) // 这里遍历到n-1是因为下面填next数组的时候是next[i + 1]
{
if(k == -1 || sub[i] == sub[k])
{
// 如果k==-1（表示出界）或者当前两个字符相等的话，则进行赋值
next[i + 1] = k + 1;
++i;
++k;
}
else
{
// 否则跳到next数组当前位置所指的前个位置
k = next[k];
}
}
}
int KMP(const string& str, const string& sub)
{
// 特殊情况处理
if(str.empty() || sub.empty())
return -1;
int str_size = str.size();
int sub_size = sub.size();
// 创建next数组，初始化为0
vector<int> next(sub_size, 0);
getNext(sub, next, sub_size);
int i = 0; // 遍历主串
int j = 0; // 遍历子串
while(i < str_size && j < sub_size)
{
if(j == -1 || str[i] == sub[j])
{
// 如果j==-1（表示出界）或者当前两个字符相等的话，则向后走
i++;
j++;
}
else
{
// 否则跳到next数组当前位置所指的前个位置
j = next[j];
}
}
if(j < sub_size)
return -1;
return i - j;
}
int main()
{
string str = "abcababcabc";
cout << KMP(str, string("abcabc")) << endl;
cout << KMP(str, string("abc")) << endl;
cout << KMP(str, string("abcd")) << endl;
cout << KMP(str, string("--")) << endl;
cout << KMP(str, string("")) << endl;
return 0;
}4、next数组的优化
有如下串：aaaaaaaab，他的 next 数组是 [-1, 0, 1, 2, 3, 4, 5, 6, 7]。
而通过优化后得到的数组 nextval 是：[-1, -1, -1, -1, -1, -1, -1, -1, 7]！
假设在 5 号下标失败了，那退一步还是 a，还是相等，接着退还是 a。这就导致了需要遍历很长的一个情况，所以我们就做如下图所示处理：
练习：模式串 t=‘abcaabbcabcaabdab’ ，该模式串的 next 数组的值为（ D ），nextval 数组的值为 （F）。
A． 0 1 1 1 2 2 1 1 1 2 3 4 5 6 7 1 2 B． 0 1 1 1 2 1 2 1 1 2 3 4 5 6 1 1 2
C． 0 1 1 1 0 0 1 3 1 0 1 1 0 0 7 0 1 D． 0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2
E． 0 1 1 0 0 1 1 1 0 1 1 0 0 1 7 0 1 F． 0 1 1 0 2 1 3 1 0 1 1 0 2 1 7 0 1
这里的起始设置默认从 0 开始，整个数组加 1 即可找出选项答案。