关于KMP算法的理解

Happyunlimited 2019-11-08

前言

本篇博客的字符串下标是从1开始的。

引入

给出两个字符串\(A,B\),询问\(B\)是否是\(A\)的子串。

对于以上问题,我们有一个比较暴力的想法,就是一位一位去配对呀。
给出代码:

int Check(){
    for(int i=1;i+M-1<=N;i++){
        int j=0;
        while(j<M&&A[i+j]==B[j+1])j++;
        if(j==M)return 1;
    }
    return 0;
}

但是显然,这个算法并不太优秀。(可以被卡到\(O(N\cdot M)\)
(尽管对于大多数题够用了)
引入KMP算法。

P1(定义)

对于A=ababababcB=ababc的例子,我们观察一下Check函数的过程。
关于KMP算法的理解
第一步,两个字符串可以配对到abab(绿边),直到遇到ac,发现不能配对(红边)。此处贡献4步。
关于KMP算法的理解
第二步,两个字符串再次配对到abab,并再次不能配对,贡献4步。
关于KMP算法的理解
第三步,两个字符串完全配对,出解,并再次贡献4步。

注:以上贡献次数指除开了遍历了一次a串的步数。


考虑对以上过程优化。
可以发现,我们在第一步失配时,完全可以直接跳到下图的情况。
关于KMP算法的理解
即我们的j的下标完全可以从4跳到2(失配前的下标)。

即我们如果能够处理出关于B串的一个数组,使得我们可以进行刚才的跳跃操作就好了。

于是乎,我们定义一个 \(Next\) 数组:
\(Next[i]\)表示的是满足如下条件的一个串的末端下标。
该串是\(B[1]\)~\(B[i]\)这个子串的后缀,也是该串的某个前缀,并且是满足以上两个条件的串中长度最长的串。
(限制\(Next[i]\)值不能为\(i\),即跳跃操作至少往前跳1格)。

(语言表达不好,不如来看看例子)

还是之前那个例子:(B=ababc
关于KMP算法的理解
那么在处理\(Next[4]\)时(即子串abab时),我们暴力的过程如下:
找出该子串的所有后缀(不算自己):
关于KMP算法的理解
然后找出其所有前缀(同样不算自己):
关于KMP算法的理解
发现ab为两次查找均出现过串中最长的串,故满足要求,即\(Next[4]\)的值就为\(2\)
关于KMP算法的理解

对于该例子(B=ababc)的所有\(Next\)值就是:
关于KMP算法的理解
失配时跳跃情况如下:
关于KMP算法的理解

P2(初始化)

那么我们应该如何求出\(Next\)数组呢?

考虑求解\(Next[i]\)时(假设\(Next[1]\)~\(Next[i-1]\)都求好了),我们如何用之前的状态转移。设之前的状态长这样:紫点与绿点是完全相等的两个子串,弧线表示\(Next[i-1]\),我们现在要求红点的\(Next\)值。
关于KMP算法的理解
那么我们只需要去比较一下下图的红点与橙点是否相等就行了:
关于KMP算法的理解
如果相等,那么 \(Next[i]\) 就等于 \(Next[i-1]+1\)
否则,我们就去访问下标为 \(Next[Next[i]]+1\) 的点再次比较,直到不能比较为止。
关于KMP算法的理解
因为这样的话,同样也满足\(Next\)数组的性质:
\(B[i-1]=B[Next[i-1]]=B[Next[Next[i-1]]]=...=B[Next[....]]\)
而最终求得的那个前缀,同样会是\(B[1]\)~\(B[i]\)的某个后缀。

P3(求解)

基于P1与P2的内容,P3就比较好理解了。
我们在最初那个暴力Check上改改就行了。
如果失配了,回到一个满足条件的Next[j]就行了。
原理呢,其实和P2初始化部分是一样的。

实在不懂的话,那还是举个例子吧。
对于A=ababababcB=ababc时,我们用KMP算法来做一下。
关于KMP算法的理解
发现ac失配,现在\(j=4\),考虑让\(j=Next[j]\),更改后\(j=2\),贡献为4。
关于KMP算法的理解
继续往后,发现失配,现在\(j=4\),再次让\(j=Next[j]\),更改后\(j=2\),贡献为3。
关于KMP算法的理解
情况变化成下图:
关于KMP算法的理解
最后出解,贡献为3。
关于KMP算法的理解
虽然只比暴力的总贡献少两步,但在某些恶意卡暴力的题中,还是得用KMP算法。

代码

板题

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=1000005;
int K,N,M,Next[MAXN],Ans;
char A[MAXN],B[MAXN];
void Prepare(){
    for(int i=2;i<=M;i++){//注意从2开始.
        int j=Next[i-1];
        if(B[j+1]!=B[i]&&j>0)j=Next[j];
        if(B[i]==B[j+1])j++;//判等于0的情况.
        Next[i]=j;
    }
}
int Find(){
    int i=1,j=0;
    for(int i=1,j=0;i<=N;i++){
        while(j&&A[i]!=B[j+1])j=Next[j];
        if(A[i]==B[j+1])j++;
        if(j==M){
            Ans++;
            j=Next[j];
        }
    }
}
int main(){
    scanf("%d",&K);
    while(K--){
        scanf("%s%s",B+1,A+1);
        N=strlen(A+1);M=strlen(B+1);
        Ans=0;Prepare();Find();
        printf("%d\n",Ans);
    }
}
/*
ababababc
ababc
*/

后记

关于KMP算法的时间复杂度:

Q:求解\(Next\)时,\(j\)指针难道不会跳很多次吗,这个复杂度难道不是\(O(M^2)\)吗?

A:其实可以发现,每次j=Next[j]的操作都会使当前的\(Next\)值比上一次的\(Next\)值小。
画出\(Next\)的函数图像如下:
关于KMP算法的理解
那么对于满足\(Next[i]>Next[i-1]\)\(Next[i]\)肯定都是在\(O(1)\)的时间里出解的。

而那些\(Next[i]<Next[i-1]\)\(Next[i]\)总跳跃次数并不会超过\(M\)
因为\(Next\)函数的值域是在\(M\)以内的,而且一次上升的差距肯定为1。
(即若\(Next[i]>Next[i-1]\),那么有\(Next[i]=Next[i-1]+1\)
而一次回跳至少跳1格,故总回跳次数是不会超过\(M\)次的。


Q:求解时每次失配,\(j\)指针最多还是会跳\(M\)次嘛,看似还是可以卡到\(O(N\cdot M)\)嘛。

A:实则不然,指针\(j\)每次都是和\(i\)一起变化的,只有在\(i\)加1时,\(j\)才有可能跟着加1。这样的话,\(j\)失配往回跳的总次数是不会超过\(N\)次的(每次跳都至少跳1格)。故KMP算法的时间复杂度是十分优秀的\(O(N)+O(M)=O(N+M)\)啦。

相关推荐