POJ 3461 Oulipo

kmp模板题。

#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 1000005
using namespace std;
char p[maxn],t[maxn];
int l1,l2,tt,next[maxn],ans;
void make_next()
{
memset(next,0,sizeof(next));
next[1]=0;
int cnt=0;
for (int i=2;i<=l1;i++)
{
while (cnt>0 && (p[cnt]!=p[i-1]))
cnt=next[cnt];
if (p[cnt]==p[i-1])
cnt++;
next[i]=cnt;
}
}
void match()
{
int cnt=0;
for (int i=0;i<l2;i++)
{
while (cnt>0 && t[i]!=p[cnt])
cnt=next[cnt];
if (t[i]==p[cnt])
cnt++;
if (cnt==l1)
{
ans++;
cnt=next[cnt];
}
}
}
int main()
{
scanf("%d",&tt);
for (int i=1;i<=tt;i++)
{
ans=0;
scanf("%s",p);
scanf("%s",t);
l1=strlen(p);
l2=strlen(t);
make_next();
match();
printf("%d ",ans);
}
return 0;
}