Pagini recente » Cod sursa (job #2988432) | Cod sursa (job #2084133) | Cod sursa (job #452473) | Cod sursa (job #368229) | Cod sursa (job #1558176)
#include <cstdio>
#include <cstring>
#define E 'z'-'a'
#define NMAX 1000000
#define SMAX 10000
using namespace std;
struct Trie
{
int nr;
Trie *son[E+5],*phi;
Trie()
{
phi=NULL;
nr=0;
for(int i=0; i<=E; ++i)
son[i]=NULL;
}
};
char A[NMAX+10],s[SMAX+10];
int n,i,crt,lst;
Trie *T,*v[1000010],*sol[110];
Trie *upd(Trie *B,char *s,int l)
{
int c;
if(l==0)
return B;
c=*s-'a';
if(B->son[c]==NULL)
B->son[c]=new Trie;
upd(B->son[c],s+1,l-1);
}
void findphi()
{
Trie *B,*node;
T->phi=T;
v[++lst]=T;
crt=1;
while(crt<=lst)
{
node=v[crt];
for(i=0; i<=E; ++i)
if(node->son[i]!=NULL)
{
B=node;
if(B!=T)
{
B=B->phi;
while(B!=T && B->son[i]==NULL)
B=B->phi;
if(B->son[i]!=NULL)
B=B->son[i];
v[crt]->son[i]->phi=B;
}
else B->son[i]->phi=T;
v[++lst]=v[crt]->son[i];
}
++crt;
}
}
void findnr()
{
int l,c;
l=strlen(A);
Trie *B;
B=T;
for(int i=0; i<l; ++i)
{
c=A[i]-'a';
while(B!=T && B->son[c]==NULL)
B=B->phi;
if(B->son[c]!=NULL)
B=B->son[c];
++B->nr;
}
for(int i=lst; i; --i)
v[i]->phi->nr+=v[i]->nr;
}
int main()
{
freopen("ahocorasick.in","r",stdin);
freopen("ahocorasick.out","w",stdout);
T=new Trie;
gets(A);
scanf("%d\n",&n);
for(i=1; i<=n; ++i)
{
gets(s);
sol[i]=upd(T,s,strlen(s));
}
findphi();
findnr();
for(i=1; i<=n; ++i)
printf("%d\n",sol[i]->nr);
return 0;
}