Pagini recente » Cod sursa (job #1296360) | Cod sursa (job #1772790) | Cod sursa (job #223595) | Cod sursa (job #1761700) | Cod sursa (job #1552208)
#include<cstdio>
#include<cstring>
#include<deque>
using namespace std;
struct nod
{
nod * po[30];
nod * fail,*tata;
int nrc,ans;
short int ch;
nod()
{
nrc=ans=0;ch=-1;
fail=tata=NULL;
for(int i=0;i<=26;i++)
po[i]=NULL;
};
};
char si[1000005],s2[10005];
int st,dr;
nod * root,* dq[1000000],*loc[105];
void bfs(nod * rad)
{
nod * tm;
int i;
st=dr=1;dq[1]=rad;
while(st<=dr)
{
rad=dq[st];
if(rad!=root)
{
tm=rad->tata->fail;
while(tm!=NULL)
{
if(tm->po[rad->ch]!=NULL)
{
rad->fail=tm->po[rad->ch];
break;
}
else
{
tm=tm->fail;
}
}
if(tm==NULL)
rad->fail=root;
rad->nrc+=rad->fail->nrc;
}
for(i=0;i<=26;i++)
if(rad->po[i]!=NULL)
{
dr++;
dq[dr]=rad->po[i];
}
st++;
}
}
int main()
{
freopen("ahocorasick.in","r",stdin);
freopen("ahocorasick.out","w",stdout);
int n,i,j,l,ans=0;
nod * tm;
root=new nod();
gets(si+1);
scanf("%d\n",&n);
for(i=1;i<=n;i++)
{
gets(s2+1);
l=strlen(s2+1);
tm=root;
for(j=1;j<=l;j++)
{
s2[j]-='a';
if(tm->po[s2[j]]==NULL)
{
tm->po[s2[j]]=new nod();
tm->po[s2[j]]->tata=tm;
tm->po[s2[j]]->ch=s2[j];
}
tm=tm->po[s2[j]];
}
loc[i]=tm;
tm->nrc++;
}
bfs(root);
tm=root;
l=strlen(si+1);
for(i=1;i<=l;i++)
{
si[i]=si[i]-'a';
while(tm->po[si[i]]==NULL && tm!=root)
{
tm=tm->fail;
}
if(tm->po[si[i]]!=NULL)
{
tm=tm->po[si[i]];
if(tm->nrc>0)
tm->ans++;
}
}
for(i=dr;i>=1;i--)
if(dq[i]->fail!=NULL)
{
dq[i]->fail->ans+=dq[i]->ans;
}
for(i=1;i<=n;i++)
printf("%d\n",loc[i]->ans);
return 0;
}