单模式串匹配算法 — KMP

KMP

看毛片KMP算法

KMP算法作为一个单模式串匹配算法,以$ O(n+m) $ 的时间复杂度俯视众生吊打各路匹配算法

但是其扩展性的艰难和通用性的低下往往很少用于项目中的实现,但对于我们Oier来说速度才最重要的
KMP的代码量并不大,思维难度也并非其他玄学算法那么高,时间也很优秀,是一种值得用于搞事情的算法

算法理念

传统匹配

在普通的查询算法中,我们通常采用一下的方法:

int ans=0;
for(int i=0;i<alen;i++){
    int t=0;
    while(1){
        if(t>=blen) break;
        if(a[i+t]!=b[t]) break;
        t++;
    }
    if(t>blen) ans++;
}

模式串: ab
文本串: fdsfdfdvab

emmmmm $ O(n) $??优秀

模式串: sb
文本串: sssa

$O(nm)$???什么状况?

好吧,我们知道了,这个东西最快$O(n)$,最慢…$O(nm)$

KMP匹配

显然如果我们在上面的第二个例子中
我们如果能知道,我现在失配了,应当直接更改当前s在模式串中的位置就可以高效的完成匹配

为此,我们定义一个next数组,用「自己匹配自己」的思想，快速找到，当我们适配失败的时候，迅速找到这一位可能在模式串中的位置

这样就避免了往回的问题，大大降低了时间复杂度–$O(n+m)$

代码实现

题目链接: [https://www.luogu.org/problemnew/show/P3375]

#include <cstdio>
#include <cstring>
using namespace std;
int kmp[11000000];
char a[1100000],b[1100000];
int main(){
    scanf("%s",a+1);
    scanf("%s",b+1);
    int alen=strlen(a+1);
    int blen=strlen(b+1);
    int k=0;
    for(int i=2;i<=blen;i++){
        while(k>0&&b[i]!=b[k+1]) k=kmp[k];
        if(b[i]==b[k+1]) k++;
        kmp[i]=k;
    }
    k=0;
    for(int i=1;i<=alen;i++){
        while(k>0&&a[i]!=b[k+1]) k=kmp[k];
        if(a[i]==b[k+1]) k++;
        if(k==blen) {printf("%d\n",i-blen+1);k=kmp[k];}
    }
    for(int i=1;i<=blen;i++) printf("%d ",kmp[i]);
}

KMP 求最小循环节

「KMP这个算法，一般很少考板子题，他通常会给你出一些思维型的，比如，next数组的妙用….」

Next数组的思想不单在KMP中很有用，在对付其他字符串处理问题甚至多模式串匹配中，我们仍将见到他的身影

比如求一个串的最小循环节

很显然len-next[len]即为循环节长度

• 如果$ len \mod len-next_{len} = 0 $ 则表明字符串是完全由循环解循环构成
• 如果不是说明需要添加，如果设循环节长度为$L$,则添加的字母个数$ L-len%L = L-next[len]%L $

当然不止这些，至于还有什么吗wq你总会遇到的啦

End

最后，祝rp++

]]>