字符串匹配算法KMP详解

RT，今日十分地无聊，刷了一波水题，在刷水题的过程中也发现了不少问题，下面顺便对KMP进行一个小讲解

原理

首先，KMP是一个字符串匹配算法，这个应该周所周知。它的思路大概是对模式串构造一个类似于状态机一样的东西，构造出它的失配函数以及失配边，然后在字符串匹配的时候进行快速转移的一个算法

构造失配函数时，有一个十分误导的说法，叫做自己匹配自己，这个虽然是有那么点感觉，但其实对学习毫无帮助，只是用来应付萌新的问题的东西。。。

其实就是通过观察性质进行递推的过程，鉴于网上相关资料已经很多，具体过程可参考代码

代码

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define maxn1 1000005
#define maxn2 10005
using namespace std;
char txt[maxn1],tem[maxn2];
int len1,len2,ans=0;
int f[maxn2];
void init(){
    len1=strlen(txt);
    len2=strlen(tem);
    f[0]=f[1]=0;
    for(int i=2;i<=len2;i++){
        int k=f[i-1];
        while(k!=0&&tem[k]!=tem[i-1]) k=f[k];
        f[i]=(tem[k]==tem[i-1])?k+1:0;//注意这个地方很重要
    }
    return;
}
void KMP(){
    int pos=0;
    for(int i=0;i<len1;i++){
        while(pos!=0&&txt[i]!=tem[pos]){
            pos=f[pos];
        }
        if(txt[i]==tem[pos])
            pos++;
        if(pos==len2){
            pos=f[pos];
            ans++;
        }//为了方便，特意构造了一个f[len2]
    }
}
int main(){
    /*freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);*/
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%s\n%s",tem,txt);
        init();
        KMP();
        printf("%d\n",ans);
        ans=0;
    }
    return 0;
}

细节

主要有如下：

1.正如上方“注意这个地方很重要”所言，那里的 k+1 一定不能写错
2.为了匹配时的方便，我们可以计算一个额外的 f[len2] ，便于匹配成功后的转移

应用

它的应用中最常见的就是 O(n) 时间内求出字符串匹配结果，然而它还可以用于快速求出字符串的所有的 Border ，如果不知道就算了有时间可能会予以补充

例题

基本都是一些水题，下面会链上题解