Pagini recente » Cod sursa (job #530701) | Cod sursa (job #1534793) | Cod sursa (job #1410977) | Cod sursa (job #2091047) | Cod sursa (job #661966)
Cod sursa(job #661966)
#include<cstdio>
#include<vector>
#include<deque>
#define LST vector<int>
#define IT vector<int>::iterator it
using namespace std;
struct lst{int inf;lst *urm;lst(){inf=0;urm=0;}};
struct nod
{
lst *L;
int ap;
nod *S[26],*fail;
nod()
{
L=0;
ap=0;
for(int i=0;i<26;i++)
S[i]=0;
fail=0;
}
}
;
nod *root,*poz[110],*Q[1000000];
int n,i,Ap,b,t;
char P[1000010],C[10010];
void read(),fail(),upd(nod*,char*),load(),solve();
int main()
{
read();
solve();
return 0;
}
void solve()
{
fail();
load();
for(t--;t>=0;t--)Q[t]->fail->ap+=Q[t]->ap;
for(i=1;i<=n;i++)printf("%d\n",poz[i]->ap);
}
void read()
{
char *c;nod *N;lst *NL;int k;
freopen("ahocorasick.in","r",stdin);
freopen("ahocorasick.out","w",stdout);
scanf("%s",P);scanf("%d",&n);
root=new nod;
for(i=1;i<=n;i++)
{
scanf("%s",C);
for(c=C,N=root;*c;c++)
{
k=*c-'a';
if(!N->S[k]){N->S[k]=new nod;NL=new lst;NL->inf=k;NL->urm=N->L;N->L=NL;}
N=N->S[k];
}
poz[i]=N;
}
}
void fail()
{
nod *aux,*faux;lst *laux;
root->fail=root;
for(laux=root->L;laux;laux=laux->urm)
{
root->S[laux->inf]->fail=root;
Q[t++]=root->S[laux->inf];
}
b=0;
for(;b<t;)
{
aux=Q[b++];
for(laux=aux->L;laux;laux=laux->urm)
{
for(faux=aux->fail;;faux=faux->fail)
{
if(faux->S[laux->inf]){aux->S[laux->inf]->fail=faux->S[laux->inf];break;}
if(faux==root){aux->S[laux->inf]->fail=root; break;}
}
Q[t++]=aux->S[laux->inf];
}
}
}
void load()
{
nod *N;char *c;
for(c=P,N=root;*c;)
{
if(N->S[*c-'a']){N=N->S[*c-'a'];N->ap++;c++;continue;}
if(N==root){c++;continue;}
N=N->fail;
}
}