KMP算法
- 1.什么是KMP算法
- 2.KMP算法能解决哪些问题
- 3.KMP算法是如何运行的
- 4.KMP算法是如何进行跳的
- 5.如何求取前缀表
- 6.KMP算法的实现
强烈推荐Carl老哥的视频！！！
多看几遍肯定是可以学会的。
理论篇——帮你把KMP算法学个通透！（理论篇）_哔哩哔哩 (゜-゜)つロ 干杯~-bilibili
求Next数组代码篇——帮你把KMP算法学个通透！（求next数组代码篇）_哔哩哔哩 (゜-゜)つロ 干杯~-bilibili 欢迎访问我的小站——半生瓜のblog同步更新哦。
1.什么是KMP算法
KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。(百度百科)
2.KMP算法能解决哪些问题
解决字符串匹配问题
给出文本串和模式串，用两层for循环进行匹配，进行暴力匹配，时间复杂度是O(m,n).其中m是模式串长度，n是文本串长度。
3.KMP算法是如何运行的
给出两个要匹配的串，文本串和模式串。
第一次匹配
第二次匹配
跳到b处继续进行匹配。
这就是KMP算法。
4.KMP算法是如何进行跳的
用到了很重要的表——前缀表。
那么，KMP算法为什么不用hash表或者其它表呢?
前缀表的特性：
- 如何实现：当进行到不匹配的元素时，找到该元素前面的字串，找到一组相等的前后缀，在该前缀的后面进行第二次匹配，就跳过去了。其实就是找最长相等前后缀的长度，从这个以这个长度为下标的元素开始进行匹配。
- 前缀：包括首元素不包括尾元素的所有字串，都称为前缀。
- 后缀：包括尾元素不包括首元素的所有字串，都称为后缀。
5.如何求取前缀表
- 求最长相等(公共)前后缀
- a的最长相等(公共)前后缀是0
aa的最长相等(公共)前后缀是1
aab的最长相等(公共)前后缀是0
aaba的最长相等(公共)前后缀是1
aabaa的最长相等(公共)前后缀是2
aabaaf的最长相等(公共)前后缀是0
所以得出此模式串的前缀表是010120
- 得到最长相等(公共)前后缀是2
- 2意味着：这里有一个后缀aa,前面有一个与其相等的前缀aa。
- 在后缀(aa)的后面(是f)后面不匹配(冲突)了。
- 就找与其相等的前缀(前面那个aa)后面那个元素(b)开始匹配。
- (其实就是从最长相等前后缀的长度下标开始。)
- (此模式串最长相等前后缀是2，就从该模式串下标为2的元素开始匹配。)
- (2表示的是最长相等前后缀的长度，我们要跳到前缀的后面，前缀的后面的下标正好是前缀的长度，因为串的下标是从0开始的。)
- 匹配成功,完成匹配过程。
流程图:
6.KMP算法的实现
有的做法会将前缀表进行一些调整，但总的思想是相同的。
有的用next数组，有的用perfix，这里用的Next数组。
碰到了冲突的位置，我们要向前回退，这是Next数组的核心所在。
对于实现，不同的人有不同的方法。
这里就用前缀表作为我们的Next数组。
求出来的Next数组就是该模式串的前缀表。
那么具体的代码应该怎么写呢？
明确求Next数组有几个步骤
1.初始化
2.处理前后缀不同的情况
3.处理前后缀不相同的情况
4.更新Next数组的值
j指向前缀末尾位置(还代表着i之前包括i,字串的最长相等前后缀的长度)。
i指向后缀末尾位置。
void getNext(int* next,const string&S)//S为模式串，（此代码类似于伪代码）
{
//1.初始化
int j = 0;//j初始化为0，前缀一开始是从开始的位置开始。
next[0];//next数组初始位置也是0。
//初始化完成
//i的初始化就进入到我们的循环遍历里了
//因为要比较前后缀所对应的字符是否相等，那i就应该是从1开始，这样i和j才能进行比较
for(int i = 1;i<S.size;i++)
{
//2.处理前后缀不相同情况
//遇到不匹配看前一位
//这里的while容易写成if，我们回退的过程并不是一步就完事的
//要判断前一位所以j>0
//否则产生负数会造成数组越界
while(j > 0 && S[i] != S[j])
{
j = next[j-1];
}
//3.处理前后缀相同的情况
//这时候j应该+1，因为j不仅代表着前缀末尾的位置，还代表着i以及i之前这个字串的最长相等前后缀的长度。
if(S[i] == S[j])
{
j++;
}
//更新Next数组
next[i] = j;
//在循环里面,i++，向后面走一位
}
}