Pagini recente » Cod sursa (job #2100540) | Istoria paginii utilizator/realjuve7 | Statistici Rusuc Amalia (RusucAmalia) | Statistici Ioana Livia Popescu (IoanaLiviaPopescu2) | Cod sursa (job #1574181)
#include<cstdio>
#include<cstring>
using namespace std;
int n,nr,m[104];
char s[1000004],sir[103][10003];
struct trie
{
int val;
trie *urm[26];
trie *phi;
trie()
{
val=0;
phi=0;
memset(urm,0,sizeof(urm));
}
}*r,*p,*aux,*q[1000004];
int main()
{
freopen("ahocorasick.in","r",stdin);
freopen("ahocorasick.out","w",stdout);
gets(s);
m[0]=strlen(s);
scanf("%d\n",&n);
r=new trie;
for(int i=1;i<=n;i++)
{
gets(sir[i]);
m[i]=strlen(sir[i]);
p=r;
for(int j=0;j<m[i];j++)
{
if(p->urm[sir[i][j]-'a']==0) p->urm[sir[i][j]-'a']=new trie;
p=p->urm[sir[i][j]-'a'];
}
}
r->phi=r;
nr=0;
for(int i=0;i<26;i++)
if(r->urm[i]!=0)
{
nr++;
q[nr]=r->urm[i];
q[nr]->phi=r;
}
for(int i=1;i<=nr;i++)
{
for(int j=0;j<26;j++)
if(q[i]->urm[j]!=0)
{
nr++;
q[nr]=q[i]->urm[j];
aux=q[i]->phi;
while(aux!=r&&aux->urm[j]==0)
aux=aux->phi;
if(aux->urm!=0)aux=aux->urm[j];
q[nr]->phi=aux;
}
}
aux=r;
for(int i=0;i<m[0];i++)
{
while(aux!=r&&aux->urm[s[i]-'a']==0)
aux=aux->phi;
if(aux->urm[s[i]-'a']!=0)
aux=aux->urm[s[i]-'a'];
aux->val++;
}
for(int i=nr;i>1;i--)
q[i]->phi->val+=q[i]->val;
for(int i=1;i<=n;i++)
{
aux=r;
for(int j=0;j<m[i];j++)
aux=aux->urm[sir[i][j]-'a'];
printf("%d\n",aux->val);
}
return 0;
}