Cod sursa(job #1509061)

Utilizator mihail.jianuJianu Mihail mihail.jianu Data 23 octombrie 2015 14:27:16
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include<cstdio>
#include<cstring>
struct N{int a;N *l[26],*x;N(){memset(this,0,sizeof(N)),memset(l,0,26);}};int i,n,j,p,u;char e[1000001],a[10001],*k;N *c[100000001],*s,*r=new N(),*cn,*b[100],*t;void A(N *r){if(!(*k)){b[j]=r;return;}*k-='a';if(!r->l[*k])r->l[*k]=new N();A(r->l[*k++]);}int main(){freopen("ahocorasick.in","r",stdin),freopen("ahocorasick.out","w",stdout);gets(e),scanf("%d\n",&n);for(j=0;j<n;j++)gets(a),k=a,A(r);r->x=c[u++]=r;while(p<u){t=c[p++];for(i=0;i<26;i++)if(t->l[i]){s=t->x;while(s!=r&&!s->l[i])s=s->x;if(s->l[i]&&s->l[i]!=t->l[i])t->l[i]->x=s->l[i];else t->l[i]->x=r;c[u++]=t->l[i];}}for(cn=r,i=0;e[i];i++){while(!cn->l[e[i]-'a']&&cn!=r)cn=cn->x;if(cn->l[e[i]-'a'])cn=cn->l[e[i]-'a'];cn->a++;}for(i=u-1;i>=0;i--)c[i]->x->a+=c[i]->a;for(i=0;i<n;i++)printf("%d\n",b[i]->a);return 0;}