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