学步园

   题意：给定两个字符串，求在主串中模式串出现的次数。

#include<stdio.h>

char A[1000005],B[10005];
int next[10005];

void getnext()
{
    int i,j;
    next[0]=0;
    for(i=1,j=0;B[i];i++)
    {
        while(j>0&&B[i]!=B[j])
            j=next[j-1];
        if(B[i]==B[j])
            j++;
        next[i]=j;
    }
}

int KMP()
{
    int ans,i,j;
    for(i=j=ans=0;A[i];i++)
    {
        while(j>0&&A[i]!=B[j])
            j=next[j-1];
        if(A[i]==B[j])
        {
            j++;
            if(!B[j])
            {
                //此处不能写j=0
                j=next[j-1];
                ans++;
            }
        }
    }
    return ans;
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s%s",B,A);
        getnext();
        printf("%d\n",KMP());
    }
    return 0;
}