参考课程：宋会英老师——KMP算法——效率较高的匹配算法
D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法
纲要
- BF算法
- KMP算法
- 失败函数（next）的定义
- 算法的特点
- 改进NEXT值
- 代码实现
在KMP算法的比较过程中，不产生回溯，匹配失败时，主串的指针不回溯，只要是在模式串中找到合适的字符（由失败函数确定）与其比较即可，故算法的渐进时间复杂度为O(n)。
KMP算法
传统的模式匹配算法（BF算法）
思想：
将目标串的第一个字符与模式串的第一个字符比较，若相等继续比较后续的字符。若不等，从第目标串的第二个字符重新和模式串的第一个字符比较。
以此类推直到模式串对应的字串。
代码实现：
int BFindex(string t,string p){
if(t.length()<1||p.length()<1){
return -1;
}
int i = 0;
int j = 0;
while(i<t.length()&&j<p.length()){
if(t[i] == p[j]){
i++;
j++;
}else{
i = i - j + 1;//i回溯
j = 0;
}
}
if(j>=p.length()){
return i-p.length();
}
return 0;
}
复杂度分析：
每次匹配失败需要回溯，需要大量的重复匹配，复杂度为O(n*m)。
回溯的问题
（图片来源:严蔚敏数据结构11教程）
首先我们引入，需要了解后缀与前缀的概念（之后会有解释），当模式串和目标串匹配时，如果第一个元素不同，自然没有回溯问题，i会移动到下一个字符，当匹配到的字符数大于1的时候，一旦匹配失败，j需要回到0，而i需要回到匹配刚开始的下个位置进行重新匹配。如下图，当匹配很长一串都相同的时候，还需要回溯到第2个位置。
那么这个回溯是否必要呢？，在重新匹配的过程中，其实很多次匹配我们已经能确定无法匹配。经过分析，我们发现只有当完成匹配的模式串的字串真后缀和真前缀相同时，从后缀开始的地方进行匹配才有可能匹配成功（认真分析一下滑动模式串匹配的过程，就能发现只有真前缀和真后缀相同，从后缀开始的地方才有可能匹配，否则在模式串已匹配部分与目标串就不匹配了），如果不相等，之前的匹配都是多余的。那么既然i之前的位置可以确定匹配状态，那么i自然不需要回溯了，只需要让模式串的某个位置j开始继续匹配i就行了（下见KMP算法）
KMP匹配算法
算法的基本思想
KMP算法最大的改进之处，在匹配失败时，主串中的指针 i 不需要回溯，而是在模式中找到适当的字符继续比较。
KMP算法的过程
在分析kmp算法之前，看看kmp匹配的过程。
当匹配失败时，找到一个Pk与ti进行比较。如何找到这个Pk就是KMP算法的关键。
KMP算法关键( k需要满足的条件)
其实就是黄色部分需要相等。那么接下来可以理解成将模式串滑动到对应位置再对Pk和ti进行比较（滑动后黄色部分对应，也就是k之前已经匹配成功了）。
进一步分析，如果匹配到不等于
，那么一定能得到的是
，与t串对应的字符一定是相等的（只有相等才能匹配到i，j位置）。如下图：
我们需要找的k的位置，需要满足p粉色段等于t的红色段，就可以滑动了。
我们可以得到红色部分一定是相等的。那么假设p段粉色部分等于p段的红色部分，那么就可以得到p段的粉色部分等于t段的红色部分。此时我们就可以发现，求k似乎与目标串无关，只与模式串有关。
k值是什么？
对于k值是什么，在之前回溯的问题的分析已经有提到了，k值自然就是真前缀的分割点或者是长度。（简单分析可知，一定要得到的是最长真前缀，这里不做分析）。
上面提到了一个很重要的一点，k值是与目标串无关的
如何得到k值——失败函数(next)
在很多博客中没有提到失败函数这个词，在看的时候云里雾里，不明白这个next到底是什么。在宋会英老师的课程中，提到的这个词，有种豁然开朗的感觉。
现在我们知道，当我们匹配失败的时候不需要回溯i，那么匹配失当j位置匹配失败的时候（为什么是j不是i，因为k只与模式串有关），就对应了一个唯一k值。形成一一映射的关系。
- j位置的失败函数，需要看的是1~j-1序列
-
所以有两个固定的值 j=0时，k=-1;j=1时，k=0；
由上我们可以给出定义：
利用失败函数进行匹配处理
-
例子：
KMP算法特点
- 效率高
- 不回溯
- 对目标串只需要扫描一遍（边读边匹配）。
对NEXT的改进
我们看一个为改进NEXT的KMP匹配的例子
我们发现，当
代码实现
void getNEXT(){
int k,j;
k = -1;j = 0;NEXT[0] = -1;
while(j<plen){
if(k==-1||P[k] == P[j]){
NEXT[++j] = ++k;
if(P[j] == P[k]){
NEXT[j] = NEXT[k];
}
}else{
k=NEXT[k];
}
}
}
int KMP_Count(){
int ans = 0;
int i = 0;
int j = 0;
getNEXT();
while(i<tlen){
if(j==-1||T[i] == P[j]){
i++;
j++;
}else
{
j = NEXT[j];
}
if(j == plen){
ans ++;
j = NEXT[j];
}
}
return ans;
}
int KMP_Index()
{
int i = 0, j = 0;
getNEXT();
while(i < tlen && j < plen)
{
if(j == -1 || T[i] == P[j])
{
i++; j++;
}
else
j = NEXT[j];
}
if(j == plen)
return i - plen;
else
return -1;
}
- 参考了kuangbin的模板，在基础上改进了next（原模板的count方法就需要修改了）。
网友评论