算法练习：KMP

#include<iostream>
#include<cstring>
using namespace std;

const int N=1010;
char s[N],p[N];
int ne[N];

int main()
{
    while(cin>>s+1)
    {
        if(s[1]=='#' && s[2]=='\0') break; //读入结束：仅一个#字符
        cin>>p+1;
        int m=strlen(s+1);
        int n=strlen(p+1);
        //求next数组
        for(int i=2,j=0;i<=n;i++)
        {
            while(j && p[i]!=p[j+1]) j=ne[j];
            if(p[i]==p[j+1]) j++;
            ne[i]=j;
        }
        //匹配过程
        int cnt=0;
        for(int i=1,j=0;i<=m;i++)
        {
            while(j && s[i]!=p[j+1]) j=ne[j];
            if(s[i]==p[j+1]) j++;
            if(j==n)
            {
                cnt++;
                j=0; //因为上一个匹配成功的布条就没了，所以每当匹配成功后进入下一个匹配时应该将模式串从头开始再继续跟长文本匹配，而j不能再根据next数组更新
            }
        }
        cout<<cnt<<endl;
    }
    return 0;
}