Pagini recente » Cod sursa (job #2383269) | Cod sursa (job #2207276) | Cod sursa (job #2128868) | Cod sursa (job #2139453) | Cod sursa (job #2974897)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
#pragma GCC optimize("unroll-loops")
#pragma gcc optimize("Ofast")
///#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();
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";
if(i<n)
for(j=0;j<=saiz;j++)
p[j]=0;
}
return 0;
}