记录编号	153937	评测结果	A
题目名称	[POJ 3461] 乌力波	最终得分	100
用户昵称	helloworld123	是否通过	通过
代码语言	C++	运行时间	0.306 s
提交时间	2015-03-20 14:24:06	内存使用	0.35 MiB

#include <bits/stdc++.h>
using namespace std;

int next[10001];
int n,ans,len;
string s1,s2,a,b;

void getss()
{
    int j=0; next[1]=0;
    for (int i=2; i<=len; i++)
    {
        while (j!=0&&a[j+1]!=a[i]) j=next[j];
        if (a[j+1]==a[i]) j++;
        next[i]=j;
    }
}
void zuo()
{
    int j=0;
    for (int i=1; i<=b.length()-1; i++)
    {
        while (j!=0&&a[j+1]!=b[i]) j=next[j];
        if (a[j+1]==b[i])
        {
            j++;
            if (j==len) ans++;
        }
    }
}
int main()
{
    freopen("oulipo.in","r",stdin);
    freopen("oulipo.out","w",stdout);
    scanf("%d",&n);

    for (int i=1; i<=n; i++)
    {
        ans=0;
        cin>>s1>>s2;
        memset(next,0,sizeof(next));
        a=" "; b=" ";
        a=a+s1; b=b+s2;
        len=a.length()-1;
        getss();
        zuo();
        cout<<ans<<endl;

    }
    return 0;
}