Pagini recente » Cod sursa (job #1216141) | Cod sursa (job #1157027) | Cod sursa (job #1424091) | Cod sursa (job #991498) | Cod sursa (job #831393)
Cod sursa(job #831393)
#include<cstdio>
#include<cstring>
using namespace std;
int i,j,l,n,nr,l1[109];
char sir[1000004],s[109][10009];
struct nod
{
int ap;
nod *urm[26];
nod *phi;
nod()
{
memset(urm,0,sizeof(urm));
phi=0;
ap=0;
}
};
nod *aux,*t,*p,*q[1000004];
int main()
{
freopen("ahocorasick.in","r",stdin);
freopen("ahocorasick.out","w",stdout);
gets(sir+1);
l=strlen(sir+1);
scanf("%d\n",&n);
t=new nod;
for(i=1;i<=n;i++)
{
gets(s[i]+1);
l1[i]=strlen(s[i]+1);
p=t;
for(j=1;j<=l1[i];j++)
{
if(p->urm[s[i][j]-'a']==0) p->urm[s[i][j]-'a']=new nod;
p=p->urm[s[i][j]-'a'];
}
}
//////////////////////////////bf si phi-ul
t->phi=t;
nr=0;
for(i=0;i<26;i++)
if(t->urm[i]!=0)
{
nr++;
q[nr]=t->urm[i];
q[nr]->phi=t;
}
for(i=1;i<=nr;i++)
for(j=0;j<26;j++)
if(q[i]->urm[j]!=0)
{
nr++;
q[nr]=q[i]->urm[j];
aux=q[i]->phi;
while(aux!=t&&aux->urm[j]==0)
aux=aux->phi;
if(aux->urm[j]!=0) aux=aux->urm[j];
q[nr]->phi=aux;
}
/////////////////////////////calculez
aux=t;
for(i=1;i<=l;i++)
{
while(aux!=t&&aux->urm[sir[i]-'a']==0)
aux=aux->phi;
if(aux->urm[sir[i]-'a']!=0)
aux=aux->urm[sir[i]-'a'];
aux->ap++;
}
for(i=nr;i>=1;i--)
q[i]->phi->ap+=q[i]->ap;
////////////////////////////afisez
for(i=1;i<=n;i++)
{
p=t;
for(j=1;j<=l1[i];j++)
p=p->urm[s[i][j]-'a'];
printf("%d\n",p->ap);
}
return 0;
}