记录编号	182592	评测结果	A
题目名称	[POJ 3461] 乌力波	最终得分	100
用户昵称	葳棠殇	是否通过	通过
代码语言	C++	运行时间	0.074 s
提交时间	2015-08-28 15:22:56	内存使用	1.29 MiB

#include<cstdio>
#include<cstring>
using namespace std;
char msc[10005],zc[1000005];
int next[10005];
int len,l,n;
int tot,wz,first;
void NeXt()
{
    for(int i=1;i<=len;i++)
    {
        int k=next[i-1];
        while(k&&msc[i]!=msc[k])
        {
            k=next[k-1];
        }
        if(msc[k]==msc[i])
        {
            next[i]=k+1;
        }
    }
}
void clear()
{
    memset(next,0,sizeof(next));
}
int main()
{
	freopen("oulipo.in","r",stdin);
	freopen("oulipo.out","w",stdout);
	scanf("%d",&n);
    while(scanf("%s%s",msc,zc)==2)
    {
        clear();
        len=strlen(msc);
        l=strlen(zc);
        NeXt();
        int j=0,tot=0;
        for(int i=0;i<=l;i++)
        {
            while(j&&msc[j]!=zc[i])
            {
                j=next[j-1];
            }
            if(msc[j]==zc[i])
            {
                j++;
            }
            if(j==len)
            {
                tot++;
                j=next[j-1];
            }
        }
        printf("%d\n",tot);
    }
}