1. 传统字符串匹配机制
KMP是对字符串匹配优化的算法,要了解kmp算法由来应先了解传统的字符串匹配的工作机制
传统的字符串匹配机制如下:
有两个字符串,上面那个是主串
(T),下面那个是模式串
(相当于关键字,下面称为p)
要在T中查找是否含有p,我们要做的工作自然是在T和p之间各自定义一个哨兵i
和j
,各自一位一位比对,如下图
如果i和j所指的值都相同,那么两者都往前走,若是不同,如下图
此时AE不等,这时候
i
和j
都需要回溯
,i
要从之前的第3位返回到第1位,j
要从第3位返回到第0位,如图
然后重复上述比较过程,这就是传统的字符串匹配过程.
传统字符串匹配的缺点
若匹配到不等的情况时,i和j都要回溯,这样一来重复无意义的比较次数很多,导致整个算法效率低下
2.KMP算法的匹配机制
在这种情况下,主角KMP
要出场了,KMP比传统字符串匹配的优秀之处就是保证i不回溯,一直勇往直前,而努力考虑匹配不成功时,j最佳的回溯位置,以此尽量减少重复无意义的比较
而KMP最精彩也是最难以理解的部分就是j最佳回溯位置的确定
,
T和P匹配成功:
不管是传统的还是在kmp中,只要匹配成功都是i
和j
同时加1,往前走T和P匹配失败(整个KMP的优化工作全在这体现):
此时保证i不回溯,j回溯到事先确定得到的最佳回溯位置next[j]
,即模式串中到j
下标时,T[i]!=P[j]
,则i不动,j回溯到next[j]位置,
然后再来比较T[i]和P[next[j]]的值
那么怎么得到保存了匹配失败
时j
的最佳回溯位置的next[]数组
呢
如图,我们先来找规律,此时c和d不相等
若是个聪明人就会做如下的比较,而不是i和j都回0位置
下图也是如此
i
不动,j
回溯到第2位
同志们,看到这里就又回到中学时期,根据给出的有限的两种图找出j位置
的一般性规律了
##j位置的一般性规律如下图
##
图中
k
,即为当i
和j
匹配失败时,j
最佳的回溯位置
-
值得强调的是:
next数组只和模式串p有关,跟主串没半毛钱关系
-
j
回溯位置k
的描述p[0~k-1]==p[j-k~j-1]
k
的位置要满足这样一个特性,即p[0~k-1]
的序列要和p[j-k~j-1]
的序列完全相同,白话文就是,p序列从0位置到k-1位置之间共k个字符的序列要和j前面k个序列相等
- 讲了这么多next数组,但一定要记住**
next数组的值就是当i和j匹配失败时,j下一步要回到的位置(即为next[j])
**
3. KMP代码
#include <iostream>
#define maxSize 100
void getNext(char ch[],int n,int *next){//得到next数组
int j,k;//next数组的作用就是当模式串和主串在模式串j位置不匹配时,j应回溯到next[j]
j=0;k=-1;
next[0]=-1;
while(j<n-1){
if(k==-1||ch[j]==ch[k]){
k++;
j++;
next[j]=k;
}else{
k=next[k];
}
}
}
int KMP(char ch[],int n,char p[],int m){
int i,j;
i=j=0;
int next[maxSize];
getNext(ch,n,next);
while(i<m&&j<n){
if(j==-1||ch[j]==p[i]){//next[0]=-1; 下标为0的位置,模式串指针不能再往左移了
i++;
j++;
}else{
j=next[j];
}
}
if(j==n){//最后若是匹配成功,j和i都是为各自的字符串长度
return i-j;//返回的是主串开始匹配的位置
}else{
return -1;
}
}
int main(int argc, char** argv) {
char p[]={'a','c','a','b','b','e'};
char ch[]={'b','b'};
int result=KMP(ch,2,p,6);
printf("%d",result);
return 0;
}
4.代码解析
以上代码很简洁有木有,但getNext
函数部分依旧晦涩的很,以下用图来剖析他的意图
i
和j
匹配失败,按道理应该i
不动,回溯j
,但j
左边没有值了,只能是i向右走一步
,所以才有next[0]=-1
的初始化
那要是j=1
处匹配失败呢?自然,j
只能回到0位置,别无可选
一般情况下,若p[k]==p[j]
(对应代码第8行情况)
此时可发现规律:(对应代码第9~11行)
当
p[k]==p[j]
时,next[j+1]==next[j]+1
不信看下图
当p[k]!=p[j]
时(代码见12行),如下图
此时代码给出的回应是(见代码13行)
k=next[k]
怎么理解这段代码?看下图
这里是整段代码中最难理解部分,给出如下阐述
为了描述方便,把上面那串叫A,下面的串叫B, 不管
p[k]与p[j]是否相等
,p[0~k-1]==p[j-k~j-1]
,即A[0~j-1]==B[0~k-1]
都成立,若是p[k]==p[j]
,那么k和j之前会拥有最长的前缀串p[0~k-1]
(即B[0~k-1]
),但由于p[k]!=p[j]
,于是乎,为了下一步的匹配,要在这最长的前缀串中砍掉几个,得到尽可能长的新前缀串,而next[k]表示p[0~t]==p[k-t~k-1]
(即B[0~t]==B[k-t~k-1]
),即B串
的前面的t个序列和从0开始的t个序列相同(t<k
),而next[j]
的存在早说明了A[0~j-1]==B[0~k-1]
,所以啊,通过等价代换可知B[0~t]=B[k-t~k-1]=A[j-t~j-1]
,即新的最长前缀串为B[0~t]
,所以k=next[k]
至此,代码中next数组的生成函数getNext的工作原理我们讲完了
,KMP函数自然是小菜一碟了
##注:此篇文章除小部分总结,其他都是借鉴孤~影大神博文##
评论区