KMP模板

#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
",KMP(ch,str));
    }
}