Cod sursa(job #1472620)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 17 august 2015 14:21:13
Problema Aho-Corasick Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 1.47 kb
#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],*v;
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(;!v->f[x[i]-'a']&&v!=t;v=v->h);
        if(v->f[x[i]-'a'])
            v=v->f[x[i]-'a'];
        ++v->m;
    }
    for(A(t),i=1;i<=n;++i)
        printf("%d\n",e[i]);
}