Pagini recente » Cod sursa (job #1084665) | Cod sursa (job #2301642) | Cod sursa (job #2454995) | Cod sursa (job #2124913) | Cod sursa (job #2974894)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
///#include <tryhardmode>
///#include <GODMODE::ON>
using namespace std;
ifstream fin ("ahocorasick.in");
ofstream fout ("ahocorasick.out");
const int NMAX=1e4+5;
int p[NMAX];
string s;
string a;
void kmp(int n)
{
int i,k=0;
for(i=1;i<n;i++)
{
while(a[i]!=a[k] && k>0)
k=p[k-1];
if(a[i]==a[k])
k++;
p[i]=k;
}
}
int main()
{
int n,m,saiz,i,j;
fin>>s>>n;
m=s.size();
for(i=1;i<=n;i++)
{
int k=0,kon=0;
fin>>a;
saiz=a.size();
for(j=0;j<=saiz;j++)
p[j]=0;
kmp(saiz);
for(j=0;j<m;j++)
{
while(s[j]!=a[k] && k>0)
k=p[k-1];
if(s[j]==a[k])
k++;
if(k==saiz)
kon++;
}
fout<<kon<<"\n";
}
return 0;
}