KMP模板

我不是女神ヾ 2022-08-10 16:34 124阅读 0赞

KMP算法是快速字符串匹配算法，朴素的暴力算法的时间复杂度为O（n\*m），而KMP通过对模式串进行相应的处理，能够达到O（m+n）的速度。

我们知道在字符串匹配的时候最消耗时间的就是当匹配到第 i 个位置发现不匹配时，下一次又对模式串进行一次重新匹配，那么假如模式串中有很多相同的字母的话，这样做了很多重复的事情，那么我可以对模式串进行一定的处理，处理处一个对应的数组，让他保存假如这里不匹配是我下次应该从哪儿重新开始。

每次当前的一个值是根据前面是否匹配的到。

这是预处理函数：

void getfill(string s)
    {
        memset(f,0,sizeof(f));  //根据其前一个字母得到
        for(int i=1;i<s.size();i++)
        {
            int j=f[i];
            while(j && s[i]!=s[j])
                j=f[j];
            f[i+1]=(s[i]==s[j])?j+1:0;
        }
    }

然后匹配函数就很好写了、

int find(string a,string s)
    {
        
        getfill(s);int j=0;
        for(int i=0;i<a.size();i++)
        {
            while(j && a[i]!=s[j])
                j=f[j];
            if(a[i]==s[j])
                j++;
            if(j==s.size()){
                return i-s.size()+1;
            }
        }
    }

顺便贴一道联系题目：

poj3461 ，求一个模式串在字符串中的出现次数。

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include <iostream>
    #include <string>
    using namespace std;
    int f[ 15000];
    void getfill(string s)
    {
        memset(f,0,sizeof(f));  //根据其前一个字母得到
        for(int i=1;i<s.size();i++)
        {
            int j=f[i];
            while(j && s[i]!=s[j])
                j=f[j];
            f[i+1]=(s[i]==s[j])?j+1:0;
        }
    }
    int find(string a,string s)
    {
        int ans=0;
        getfill(s);int j=0;
        for(int i=0;i<a.size();i++)
        {
            while(j && a[i]!=s[j])
                j=f[j];
            if(a[i]==s[j])
                j++;
            if(j==s.size()){
                ans++;
            }
        }
        return ans;
    }
    int main()
    {
        string s,a;
        int T;
        scanf("%d",&T);
        while(T--)
        {
            getchar();
            cin>>s>>a;
            int ans=find(a,s);
            printf("%d\n",ans);
        }
        return 0;
    }