首页 > 其他 > 详细

KMP模板

时间:2015-09-29 20:19:23      阅读:208      评论:0      收藏:0      [点我收藏+]
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int next[100];
void set_next(char str[])
{
    int len,j,i;
    len=strlen(str);
    next[0]=-1;
    j=-1; i=0;
    while(i<len)
    {
        if(j==-1||str[j]==str[i])
        {
            i++;j++;
            next[i]=j;
        }
        else
        j=next[j];
    }
}
int KMP(char ch[],char str[])
{
    int i,j,lenc,lens,ans=0;
    i=0; j=0;
    lenc=strlen(ch);
    lens=strlen(str);
    set_next(ch);
    while(i<lens)
    {
        if(j==-1||str[i]==ch[j])
        {
            i++; j++;
        }
        else
        {
            j=next[j];
        }
        if(j==lenc) ans++;
    }
    return ans;
}

int main()
{
    char ch[100],str[100];
    while(scanf("%s%s",str,ch)>0)//str为母串,ch为子串
    {
        printf("%d\n",KMP(ch,str));
    }
}

 

KMP模板

原文:http://www.cnblogs.com/pshw/p/4847144.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!