首页 > 代码库 > KMP模板

KMP模板

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;
}



KMP模板