Pagini recente » Cod sursa (job #615426) | Cod sursa (job #623737) | Cod sursa (job #1149147) | Rating Matei Alexandru (mateialexandru25) | Cod sursa (job #723649)
Cod sursa(job #723649)
#include<fstream>
#include<cstring>
using namespace std;
int i,j,n,m,p[10010];
char s[1000010],b[10010],c[10010];
void prefix()
{
int i,k,n1;
n1=strlen(b+1);
k=0;
p[1]=0;
for(i=2;i<=n1;++i)
{
while(k>0&&b[k+1]!=b[i])
k=p[k];
if(b[k+1]==b[i])
++k;
p[i]=k;
}
}
int det()
{
int i,k,sol=0,n1;
prefix();
n1=strlen(b+1);
k=0;
for(i=1;i<=m;++i)
{
while(k>0&&b[k+1]!=s[i])
k=p[k];
if(b[k+1]==s[i])
++k;
if(k==n1)
++sol;
}
return sol;
}
int main()
{
FILE *f=fopen("ahocorasik.in","r");
FILE *g=fopen("ahocorasik.out","w");
fscanf(f,"%s",s+1);
m=strlen(s+1);
fscanf(f,"%d",&n);
for(i=1;i<=n;++i)
{
memcpy(b,c,sizeof(b));
fscanf(f,"%s",b+1);
fprintf(g,"%d\n",det());
}
return 0;
}