Pagini recente » Cod sursa (job #793374) | Cod sursa (job #1988039) | Istoria paginii runda/6/clasament | Cod sursa (job #1054579) | Cod sursa (job #1198625)
#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;
}
//#include<cstdio>
//#define I U->inf
//using namespace std;
//struct lst
//{
// int inf;
// lst *urm;
// lst()
// {
// inf=0;
// urm=0;
// }
//};
//struct nod
//{
// lst *L;
// int A;
// nod *S[26],
// *F;
// nod(){L=0;A=0;for(int i=0;i<26;i++)S[i]=0;F=0;}};
//nod *R,*poz[110],*Q[1000000];
//int n,i,b,t;
//char P[1000010],C[10010];
//void read(),solve();
//int main(){read();solve();return 0;}
//void read()
//{
// char *c;nod *N;
// lst *NL;
// int k;R=new nod;
// freopen("ahocorasick.in","r",stdin);freopen("ahocorasick.out","w",stdout);
// scanf("%s",P);scanf("%d",&n);
// for(i=1;i<=n;i++)
// {
// scanf("%s",C);
// for(c=C,N=R;*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 solve()
//{
// nod *N;lst *U;
// char *c;
// R->F=R;
// for(U=R->L;U;U=U->urm)
// {
// R->S[I]->F=R;
// Q[t++]=R->S[I];
// }
// for(;b<t;b++)
// {
// for(U=Q[b]->L;U;U=U->urm)
// {
// for(N=Q[b]->F;;N=N->F)
// {
// if(N->S[I])
// {
// Q[b]->S[I]->F=N->S[I];break;
// }
// if(N==R)
// {
// Q[b]->S[I]->F=R;break;
// }
// }
// Q[t++]=Q[b]->S[I];
// }
// }
// for(c=P,N=R;*c;)
// {
// if(N->S[*c-'a'])
// {
// N=N->S[*c-'a'];N->A++;c++;continue;
// }
// if(N==R)
// {
// c++;continue;
// }
// N=N->F;
// }
// for(t--;t>=0;t--)
// Q[t]->F->A+=Q[t]->A;
// for(i=1;i<=n;i++)
// printf("%d\n",poz[i]->A);}