Pagini recente » Cod sursa (job #1191825) | Cod sursa (job #1389352) | Cod sursa (job #712815) | Cod sursa (job #2289879) | Cod sursa (job #1472619)
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<ctype.h>
int g,n,l,f[10005],p,u,i,o;
char x[1000005],c[10005];
typedef struct A {
int m,d[10005];
struct A *f[26],*h;
}C;
C *q[100060005],*t,*p;
C *D() {
C *a=(C*)malloc(sizeof(C));
a->m=0,a->h=NULL,memset(a->f,0,sizeof(a->f));
return a;
}
void I(C *t,char *p,int i) {
if(!isalpha(*p)) {
t->d[++t->d[0]]=i;
return;
}
if(!t->f[*p-'a'])
t->f[*p-'a']=D();
I(t->f[*p-'a'],p+1,i);
}
void B(C *t) {
C *r;
t->h=t;
for(q[p=u=1]=t;p<=u;++p) {
C *w=q[p];
for(int i=0;i<26;++i)
if(w->f[i]) {
for(r=w->h;r!=t&&!r->f[i];r=r->h);
if(r->f[i]&&r->f[i]!=w->f[i])
r=r->f[i];
w->f[i]->h=r;
q[++u]=w->f[i];
}
}
t->h=NULL;
}
void A(C *t) {
for(int i=u;i>0;--i) {
C *w=q[i];
if(w->h)
w->h->m+=w->m;
for(int j=1;j<=w->d[0];++j)
e[w->d[j]]=w->m;
}
}
int main() {
freopen("ahocorasick.in","r",stdin),freopen("ahocorasick.out","w",stdout),scanf("%s",x),scanf("%d",&n);
t=new ac;
for(i=1;i<=n;++i)
scanf("%s",c),I(t,c,i);
B(t),p=t,g=strlen(x);
for(i=0;i<g;++i) {
for(;!p->f[x[i]-'a']&&p!=t;p=p->h);
if(p->f[x[i]-'a'])
p=p->f[x[i]-'a'];
++p->m;
}
for(A(t),i=1;i<=n;++i)
printf("%d\n",e[i]);
}