Pagini recente » Cod sursa (job #610287) | Cod sursa (job #1541813) | Cod sursa (job #625344) | Cod sursa (job #166127) | Cod sursa (job #789251)
Cod sursa(job #789251)
#include <cstdio>
#include <fstream>
#include <iostream>
#include <string>
using namespace std;
int p[10001],n,sol;
string a,b,s;
void f ()
{
for(size_t i=2,q=0;i<b.size();++i)
{
for(;q&&b[i]!=b[q+1];q=p[q]);
if(b[q+1]==b[i])
++q;
p[i]=q;
}
}
int main ()
{
ifstream in ("ahocorasick.in");
freopen ("ahocorasick.out","w",stdout);
in>>s>>n;
a=" "+s;
for(;n;--n)
{
in>>s;
b=" "+s;
for(size_t i=1;i<b.size();++i)
p[i]=0;
sol=0;
f();
for(size_t i=1,q=0;i<a.size();++i)
{
for(;q&&a[i]!=b[q+1];q=p[q]);
if(a[i]==b[q+1])
++q;
if(q+1==b.size())
++sol;
}
printf("%d\n",sol);
}
return 0;
}