Pagini recente » Cod sursa (job #2725939) | Cod sursa (job #2445571) | Cod sursa (job #1129575) | Cod sursa (job #2460475) | Cod sursa (job #1148930)
#include<fstream>
#include<vector>
#include<cstring>
#define N 100100
#define M 10010
#define K 1000010
using namespace std;
ifstream f("ahocorasick.in");
ofstream g("ahocorasick.out");
int i,j,n,p,u,sol[110];
char s[N],s1[M];
struct trie{
int nr;
vector<int>care;
trie *fii[26],*urm;
trie()
{
urm=NULL;
memset(fii,0,sizeof(fii));
nr=0;
}
};
trie *t=new trie,*nod2,*nod,*q[K];
inline void insereaza(trie *t,int x,char *p){
if(!*p)
{
t->care.push_back(x);
return ;
}
if(!t->fii[*p-'a'])
{
t->fii[*p-'a']=new trie;
}
insereaza(t->fii[*p-'a'],x,p+1);
}
inline void bfs(){
q[1]=t;
p=u=1;
t->urm=t;
while(p<=u)
{
nod=q[p++];
for(i=0;i<=25;++i)
if(nod->fii[i]!=NULL)
{
for(nod2=nod->urm;nod2!=t&&nod2->fii[i]==NULL;nod2=nod2->urm);
if(nod2->fii[i]!=NULL&&nod2->fii[i]!=nod->fii[i])
nod2=nod2->fii[i];
nod->fii[i]->urm=nod2;
q[++u]=nod->fii[i];
}
}
t->urm=NULL;
}
inline void antibfs(){
for(i=u;i;--i)
{
nod=q[i];
if(nod->urm!=NULL)
{
nod->urm->nr+=nod->nr;
}
for(j=0;j<nod->care.size();++j)
sol[nod->care[j]]=nod->nr;
}
}
int main()
{
f>>s;
f>>n;
for(i=1;i<=n;++i)
{
f>>s1;
insereaza(t,i,s1);
}
bfs();
nod=t;
for(i=0;s[i];++i)
{
while(nod!=t&&nod->fii[s[i]-'a']==NULL)
nod=nod->urm;
if(nod->fii[s[i]-'a']!=NULL)
nod=nod->fii[s[i]-'a'];
++nod->nr;
}
antibfs();
for(i=1;i<=n;++i)
g<<sol[i]<<'\n';
return 0;
}