KMP算法是一种字符串匹配算法，可以再$O(n+m)$的时间复杂度内实现两个字符串的匹配。这篇主要记录一下自己对KMP算法的理解。
字符串匹配
字符串匹配问题就是:字符串P是否为字符串S的子串？如果是它出现在s的哪些位置。其中S称为模式串，P称为子串。
暴力解(Brute-Force)
对于A和B两个字符串是否相等，我们一般是首先比较长度$len(A)==len(B)$,如果长度相等的话，接着遍历$A,B$判断$A[i]==B[i]$，如果都相等话返回$true$，否则返回$false$.
bool is_equal(string A,string B){
int lenA=(int)A.length();
int lenB=(int)B.length();
if(lenA!=lenB) return false;
for(int i=0;i<lenA;i++){
if(A[i]!=B[i]) return false;
}
return true;
}
我们知道判断两个字符串是否相等，那么最暴力的字符串匹配算法氛围两步骤:
- 枚举i=0,1,2…….len(S)-len(P)
- 判断S[i,i+len(P)-1]和P作比较，如果一致，那么就找到了一个匹配
下图展示了一个例子：
下面给出c++代码：
bool bruteForce_find(string P,string S){
int lenP=(int)P.length();
int lenS=(int)S.length();
if(lenS<lenP) return false;
for(int i=0;i<=lenS-lenP;i++){
bool flag=true;
for(int j=0;j<lenP;j++){
if(S[i+j]!=P[j]){
flag=false;
break;
}
}
if(flag) return true;
}
return false;
}
可以看出，时间复杂度为$O(nm)$
KMP算法
下面看个很简单的例子，模式串P=”abcabd“，和主串进行比较，在P[5]处失配。
按照暴力解法，那肯定就是从S[1]再开始和P做比较，但是我们发现为什么不能从S[3]开始进行匹配呢，因为S[1]和S[2]肯定失配，一个开头为b,一个开头为c，肯定和P[0]也就是和a不一样。假设有这样一个next数组，可以记录在某个位置失配后下一个S开始的位置的话，那肯定可以节省一大部分时间。
next数组
next数组记录的是一个字符串的最长公共前缀和后缀。比如字符串abcab。它的前缀集合为{$a,ab,abc,acca$},它的后缀集合为{$bcab,cab,ab,b$}。那么它在next数组中对应的值为2。
那么如何求next数组呢，这里采用动态规划的方法。$next[i]$表示$ P[0]~P[x]$ 这一段字符串，使得k-前缀恰等于k-后缀的最大的k。那么我们知道$next[0],next[1]……next[x-1]$如何求$next[x]$.来分情况讨论，我们将$next[x-1]$的值称为$now$。
-
如果$P[now]==P[next]$的话，那么$next[x]=next[x-1]+1$
-
如果$P[now]!=P[next]$的话，我们需要缩小now，那么now缩小到什么时候比较合适呢
我们可以看到子串A等于子串B，那么A的后缀和B的后缀是相同的，这就意味着子串A的最长公共前后缀肯定包括了next[c]所代表的字符串。我们把now变为next[now-1]。逐渐缩小，直到为0。c++代码如下：
void getNext(string p){
int len=(int)p.length();
vector<int>next(len,0);
next[0]=0;
int i=1;
int now=0;
while(i<=len-1){
//如果相等,加一
if(p[now]==p[i]){
now=now+1;
next[i]=now;
i+=1;
}else if(now!=0){ //不相等，缩小now
now=next[now-1];
}else{ //如果now=0的话，并且P[0]不等于P[i]的话
next[i]=0;
i+=1;
}
}
}
利用next数组匹配
下面直接上代码
bool isIn(string p,string s){
//首先求next数组n
if(s==""){
return false;
}
int len=(int)s.length();
vector<int>next(len,0);
//next为第一个数字的时候就是next就是0，这个代表长度
next[0]=0;
int i=1;
int now=0;
while(i<=len-1){
if(s[now]==s[i]){
now=now+1;
next[i]=now;
i+=1;
}else if(now!=0){
now=next[now-1];
}else{
next[i]=0;
i+=1;
}
}
//接下来 kmp
int si=0;
int sj=0;
while(si<p.length()){
if(p[si]==s[sj]){
si++;
sj++;
}else if(sj!=0){
sj=next[sj-1];
}else{
si++;
}
if(sj==len){
return true;
}
}
return false;
}
