Pagini recente » Cod sursa (job #836112) | Cod sursa (job #2724097) | Cod sursa (job #2691864) | Cod sursa (job #3281744) | Cod sursa (job #1149869)
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
class trie
{
public:
vector<int> nd;
int n0;
trie *fiu[26],*fail;
trie()
{
n0=0;
fail=0;
memset(fiu,0,sizeof fiu);
}
void ins(char *l,int id)
{
if(!*l)
{
nd.push_back(id);
return;
}
int lit=*l-'a';
if(!fiu[lit])
fiu[lit]=new trie;
fiu[lit]->ins(l+1,id);
}
}*t=new trie,*q[10002];
int n,sol[100],qe;
char txt[1000002],cuv[10002];
void bfs()
{
t->fail=t;
q[++qe]=t;
for(int i=1;i<=qe;++i)
{
trie *crt=q[i];
for(int j=0;j<26;++j)
if(crt->fiu[j])
{
trie *fl=crt->fail;
while(fl!=t && !fl->fiu[j])
fl=fl->fail;
if(fl->fiu[j] && fl->fiu[j]!=crt->fiu[j])
fl=fl->fiu[j];
crt->fiu[j]->fail=fl;
q[++qe]=crt->fiu[j];
}
}
t->fail=0;
}
void kmp()
{
trie *p=t;
for(int i=0;txt[i];++i)
{
int lit=txt[i]-'a';
while(!p->fiu[lit] && p!=t)
p=p->fail;
if(p->fiu[lit])
p=p->fiu[lit];
++(p->n0);
}
}
void antibfs()
{
while(qe)
{
trie *crt=q[qe--];
if(crt->fail)
crt->fail->n0+=crt->n0;
for(size_t j=0;j<crt->nd.size();++j)
sol[crt->nd[j]]=crt->n0;
}
}
int main()
{
int i;
freopen("ahocorasick.in","r",stdin);
freopen("ahocorasick.out","w",stdout);
scanf("%s%d",txt,&n);
for(i=0;i<n;++i)
{
scanf("%s",cuv);
t->ins(cuv,i);
}
bfs();
kmp();
antibfs();
for(i=0;i<n;++i)
printf("%d\n",sol[i]);
return 0;
}