剪花布条

分析：基础的练习...............

=======================================================================================

#include<stdio.h>
#include<string.h>

const int MAXN = 1e4+7;

void GetNext(char s[], int next[], int N)
{
    int i=0, j=-1;

    while(i<N)
    {
        if(j==-1 || s[i]==s[j])
            next[++i] = ++j;
        else
            j = next[j];
    }
}
int KMP(char a[], char b[])
{
    int i=0, j=0, ans=0, next[MAXN]={-1};
    int Na=strlen(a), Nb=strlen(b);

    GetNext(b, next, Nb);

    while(i < Na)
    {
        while(j==-1 || (a[i]==b[j] && i<Na) )
            i++, j++;

        if(j == Nb)
            j=0, ans++;
        else
            j = next[j];
    }

    return ans;
}

int main()
{
    char a[MAXN], b[MAXN];

    while(scanf("%s", a), strcmp(a, "#"))
    {
        scanf("%s", b);

        printf("%d
", KMP(a, b));
    }

    return 0;
}