剪花布条 【HDU - 2087】【KMP模板题】

KMP教学链接，不懂的可以在线问

题意：

2个字符串A,B.问A中有多少个字符串B.

Input

输入中含有一些数据，分别是成对出现A,B
A和B不会超过1000个字符。
如果遇见#字符，则表示测试结束。
 

Output

输出B的个数，每个结果之间应换行。

KMP模板题：
 

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int maxN=1e3+5;
char a[maxN], b[maxN];
int nex[maxN];
void cal_next(int len)
{
    nex[0]=-1;
    int k = -1;
    for(int i=1; i<len; i++)
    {
        while(k>-1 && nex[k+1]!=b[i])
        {
            k = nex[k];
        }
        if(nex[k+1] == b[i]) k++;
        nex[i]=k;
    }
}
int KMP(int sa, int ea, int len)
{
    int k = -1;
    for(int i=sa; i<ea; i++)
    {
        while(k>-1 && a[i]!=b[k+1])
        {
            k = nex[k];
        }
        if(b[k+1] == a[i]) k++;
        if(k == len-1) return i-len+1;
    }
    return -1;
}
int main()
{
    while(scanf("%s %s", a, b)!=EOF)
    {
        if(a[0]=='#') break;
        int lena=(int)strlen(a), lenb=(int)strlen(b);
        cal_next(lenb);
        int tmp=0, now=0, ans=0;
        while(lena-now>=lenb && (tmp=KMP(now, lena, lenb))!=-1 )
        {
            ans++;
            now = tmp + lenb;
        }
        printf("%d\n", ans);
        getchar();
    }
    return 0;
}