Pagini recente » Cod sursa (job #2651228) | Cod sursa (job #132926) | Rezultatele filtrării | Rezultatele filtrării | Cod sursa (job #1198657)
#include <cstdio>
#include <cstring>
using namespace std;
struct nod
{
nod *s[26],*fail;
int cnt;
char S[26];
nod()
{
for(int i=0;i<26;i++)
s[i]=0;
fail=0;
cnt=0;
memset(S,0,sizeof(S));
}
};
nod *root,*pt,*poz[110],*Q[1000010];
char A[1000010],B[10010],*p;
int n,i,t,b;
int main()
{
freopen("ahocorasick.in","r",stdin);
freopen("ahocorasick.out","w",stdout);
scanf("%s",A);
scanf("%d",&n);
root=new nod;
for(i=1;i<=n;i++)
{
scanf("%s",B);
for(pt=root,p=B;*p;p++)
{
if(!pt->s[*p-'a'])
{
pt->s[*p-'a']=new nod;
int LG=strlen(pt->S);
pt->S[LG]=*p;
}
pt=pt->s[*p-'a'];
}
poz[i]=pt;
}
root->fail=root;
for(p=root->S;*p;p++)
{
Q[++t]=root->s[*p-'a'];
Q[t]->fail=root;
}
for(b=1;b<=t;b++)
{
for(p=Q[b]->S;*p;p++)
{
for(pt=Q[b]->fail;;pt=pt->fail)
{
if(pt->s[*p-'a'])
{
Q[b]->s[*p-'a']->fail=pt->s[*p-'a'];
break;
}
if(pt==root)
{
Q[b]->s[*p-'a']->fail=root;break;
}
}
Q[++t]=Q[b]->s[*p-'a'];
}
}
for(p=A,pt=root;*p;)
{
if(pt->s[*p-'a']){pt=pt->s[*p-'a'];pt->cnt++;p++;continue;}
if(pt==root){p++;continue;}
pt=pt->fail;
}
for(;t;t--)
Q[t]->fail->cnt+=Q[t]->cnt;
for(i=1;i<=n;i++)
printf("%d\n",poz[i]->cnt);
return 0;
}