kmp(看毛片从入门精通)

KMP概述

KMP算法,是一种对暴力单模式字符串匹配的改进算法,他可以在O(M+N)的时间内求出在文本串中模式串的出现次数和位置,具体实现利用了字符串的自匹配性,从而减少了一些不必要的比较没降低了复杂度。

原理:

/*kmp算法,最优复杂度为0(m+n),
kmp算法比传统的暴力算法的优势在于
用模串自身的匹配信息来减少不必要的
匹配,*/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
char p[1010];
char t[1010];
int Next[1010];
void getNext(char p[])
{
    int len=strlen(p);
    int k=0; //k为当前匹配长度
    Next[0]=0;
    for(int i=1;i<len;i++)
    {
        while(k&&p[i]!=p[k]) //当前匹配长度不为0且当前位实配时,需要在已匹配串中找子串,可以看做对模式串kmp,这也是为什么求next数组和kmp代码看起来一样的原因。
            k=Next[k-1];
        if(p[i]==p[k])
            k++; //递归求next数组
        Next[i]=k;
    }
    return ;
}
int kmp(char p[],char t[])
{
    int lenp=strlen(p);
    int lent=strlen(t);
    int k=0,cnt=0;
    for(int i=0;i<lent;i++)
    {
        while(k&&p[k]!=t[i])
            k=Next[k-1];
        if(t[i]==p[k])
            k++;
        if(k==lenp)
        {
            cnt++;
            k=0;
        //当匹配不可覆盖时,即每个点只能用一次,可覆盖时,next=next[i-1];
        }
    }
    return cnt;
}
int main()
{
    while(~scanf("%s%s",t,p)&&t[0]!='#')
    {
        getNext(p);
//        for(int i=1;i<strlen(p);i++)
//            cout<<next[i]<<" ";
        printf("%d\n",kmp(p,t));
    }
    return 0;
}

kmp(看毛片从入门精通)》有1个想法

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注