记录编号	460777	评测结果	AAA
题目名称	[POJ 3461] 乌力波	最终得分	100
用户昵称	Hzoi_moyi	是否通过	通过
代码语言	C++	运行时间	0.162 s
提交时间	2017-10-18 13:53:25	内存使用	3.90 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
int next[10010],n,len1,len2,ans;
char a[10010],b[1000010];
void gn()
{
     next[0]=next[1]=0;
     for(int i=1;i<len1;i++)
     {
         int j=next[i];
         while(j&&a[i]!=a[j])  j=next[j];
         next[i+1]=(a[i]==a[j])?j+1:0;
     }
}
int main()
{
    freopen("oulipo.in","r",stdin);
    freopen("oulipo.out","w",stdout);
    scanf("%d",&n);
    while(n--)
    {
        ans=0;
        scanf("%s%s",a,b);
        len1=strlen(a);
        len2=strlen(b);
        gn();
        for(int i=0,k=0;i<len2;i++)
        {
            while(k&&a[k]!=b[i]) k=next[k];
            if(a[k]==b[i])  k++;
            if(k==len1)  ans++,k=next[k];
        }
        printf("%d\n",ans);
    }
    //while(1);
    return 0;
}