目录
KMP 算法的作用，解决的问题
KMP 算法的流程
Next 数组
KMP 算法正式过程
KMP 算法的证明过程
Next 数组的求法
Next 数组求法的证明过程
KMP 算法代码
结尾
KMP 算法的作用，解决的问题
1.
首先给你一个字符串 str，然后又给你一个字符串 match，请你再 str 的子串中找，是否存在字符串与 match 匹配，如果找到了返回该子串在 str 的开始位置下标，如果没有找到返回 -1。
2.
暴力解法，遍历所有子串需要 O（N*M）的时间复杂度，KMP 算法可以只用 O（N）时间复杂度解决这个问题。
KMP 算法的流程与证明过程
Next 数组
1.
对于 match 数组的每一个元素都有一个对应的数值，存储在 next 数组中。
2.
match[i]对应 next[i]。
3.
next[i]存储的值是，i 位置前面部分的最长公共前后缀的长度。
i 位置前面部分是指 0～i-1 区间。
例如 0～i-1 区间对应字符串为 abcabc。
前缀序列指的是 a，ab，abc，abca，abcab。
后缀序列指的是 c，bc，abc，cabc，bcabc。
公共前后缀长度是指，前后缀序列相同的长度，例如 a 与 c 前后缀序列不相同，ab 与 bc 前后缀序列不相同，abc 与 abc 前后缀序列相同，长度为 3，abca 与 cabc 前后缀序列不相同，abcab 与 bcabc 前后缀序列不相同。
因此最长公共前后缀长度为 3。
4.
人为规定 next[0]=-1，next[1]=0。
KMP 算法正式过程
1.
如果 str[i～X-1]全部与 match[0～Y-1]匹配成功，此时 X 与 Y 匹配失败，Y=next[Y]，Y 回退到对应 next 存储的下标位置。
然后新的 Y 下标与 X 继续匹配。
2.
如果 next[Y]==-1，此时说明 Y==0，X++，然后新的 X 下标和 Y 继续匹配。
3.
如果 X 与 Y 匹配成功，X++，Y++，新的 X 与新的 Y 继续匹配。
4.
直到 XY 其中一个越界，如果 X 越界说明 Y 还没有匹配完，后面没有字符了，说明匹配失败，返回 -1。
如果 Y 越界，说明 Y 匹配完了，匹配成功，对应的 str 匹配子串开始下标位置是 X-Y。
KMP 算法的证明过程
1.
如果 str[i～X-1]全部与 match[0～Y-1]匹配成功，此时 X 与 Y 匹配失败，Y=next[Y]，Y 回退到对应 next 存储的下标位置。
然后新的 Y 下标与 X 继续匹配。
1.
A 部分和 B 部分相同，C 部分与 B 部分相同，说明 A 部分和 C 部分相同，Y 回退到 next[Y]位置，相当于已经匹配完 AC 部分接下来匹配红色 Y 与 X 位置元素。
2.
为什么 A 部分前面都可以不用考虑？
假设 A 部分前面开始匹配可以匹配成功，那么蓝色框框部分就是匹配成功的子串，上面蓝色部分 C 对应下面蓝色部分 C 是相同的，上面蓝色部分前面一段 C 和绿色框框 D 是相同的，也就是下面绿色 D 和蓝色 C 是相同的，那么 Y 的 next[Y]得到了一个更大的长度，我们 next[Y]最长公共前后缀是 BC 部分，现在推出一个更长的公共前后缀，推出矛盾，说明 A 部分前面都不用考虑。
Next 数组的求法
1.
假设 0～Y-1 的 next 都求完了，cn 是 Y-1 对应的 next 值。
如果 match[cn]==match[Y-1]，next[Y]=cn+1。
2.
如果 match[cn]！=match[Y-1],cn=next[cn].
然后新的 cn 继续与 Y-1 进行判断。
3.
如果 next[cn]==-1，说明 cn==0，next[Y]=0。
4.
下一次计算的时候，cn 等于 Y-1 对应的 next 值，初始化。
Next 数组求法的证明过程
1.
首先 next[Y]最大是 A 的长度，当且仅当 match[next[Y-1]]==match[Y]的时候，取得。这是 next[Y]的极限。
不可能大于这个值，如果大于说明最长公共前后缀求错了，推出时矛盾的。
2.
如果 match[cn]！=match[y-1], cn=next[cn].
此时我们在判断紫色位置有没有可能是最长公共前后缀，也就是我们跳过了蓝色区间。也就是我们需要证明蓝色位置不可能是最长公共前后缀开始的位置。
同理，如果蓝色位置有可能成为答案，那么会推出最长公共前后缀求错了，推出矛盾，所以蓝色部分是不可能的区间位置。
3.以此类推....
KMP 算法代码
#include<bits/stdc++.h>
using namespace std;
class code01_KMP {
public:
static int getIndexof(string str, string match) {
if (str.empty() || match.empty() || str.size() < match.size())
return -1;
int x = 0, y = 0;
vector<int> next = getNextVector(match);
while (x < str.size() && y < match.size()) {
if (str[x] == str[y]) {//如果相等往后移
x++;
y++;
} else if (next[y] != -1) {//如果不相等，y后退到next[y]位置
y = next[y];
} else {//如果next[y]==-1,即y==0，x++
x++;
}
}//x-a+1=y+1--->a=x-y
return y == match.size() ? x - y : -1;
}
static vector<int> getNextVector(string match) {
if (match.size() == 1) return { -1 };
vector<int> next(match.size());
next[0] = -1;
next[1] = 0;
int i = 2;//从下标为2位置开始计算next
int cn = 0;//i-1位置的next数值
while (i < next.size()) {
if (match[i - 1] == match[cn]) {//如果i-1位置字符与cn相等，cn是某个公共前后缀长度，cn+1表示next[i]
next[i++] = ++cn;
} else if (next[cn] != -1) {//如果next[cn]!=-1，cn=nect[cn]
cn = next[cn];
} else {//如果nect[cn]==-1,cn不能等于nect[cn]，next[i]==cn==0
next[i++] = 0;
}
}
return next;
}
static string getRandomString(int possibilities, int size) {//0-25
srand(time(NULL));
//string ans("", rand() % (size + 1));
string ans("", size);
for (int i = 0; i < ans.size(); i++) {
ans[i] = rand() % (possibilities + 1) + 'a';
}
return ans;
}
};
int main() {
int possibilities = 5;
int strSize = 20;
int matchSize = 5;
cout << "test begin" << endl;
string str = code01_KMP::getRandomString(possibilities, strSize);
string match = code01_KMP::getRandomString(possibilities, matchSize);
cout << "str:" << str << endl;
cout << "match:" << match << endl;
int pos = code01_KMP::getIndexof(str, match);
if (pos != -1)
cout << "匹配成功！ 开始下标：" << code01_KMP::getIndexof(str, match) << endl;
else cout << "匹配失败!" << endl;
}结尾
最后，感谢您阅读我的文章，希望这些内容能够对您有所启发和帮助。如果您有任何问题或想要分享您的观点，请随时在评论区留言。
同时，不要忘记订阅我的博客以获取更多有趣的内容。在未来的文章中，我将继续探讨这个话题的不同方面，为您呈现更多深度和见解。
谢谢您的支持，期待与您在下一篇文章中再次相遇！
