Cod sursa(job #1472674)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 17 august 2015 15:25:36
Problema Aho-Corasick Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 1.46 kb
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>
int g,n,l,a[10005],j,k,i;
char x[1000005],c[10005];
typedef struct A {
    int m,d[105],e;
    struct A *f[26],*t;
}C;
C *q[100100025],*t,*p;
C *V() {
    C *r=(C*)malloc(sizeof(C));
    r->m=0,r->t=NULL,memset(r->f,0,sizeof(r->f));
    return r;
}
void I(C *t,char *p,int i) {
    if(!isalpha(*p)) {
        t->d[t->e++]=i;
        return;
    }
    if(!t->f[*p-'a'])
        t->f[*p-'a']=V();
    ins(t->f[*p-'a'],p+1,i);
}
void bfs(C *w) {
    C *o,*u;
    w->t=t;
    for(q[j=k=1]=w;j<=k;++j) {
        u=q[j];
        for(int i=0;i<26;++i)
        if(u->f[i]!=NULL) {
            for(o=u->t;o!=t&&!o->f[i];o=o->t);
            if(o->f[i]!=NULL&&o->f[i]!=u->f[i])
                o=o->f[i];
            u->f[i]->t=o,q[++k]=u->f[i];
        }
    }
    w->t=NULL;
}
void A(C *t) {
    for(int i=k;i;--i) {
        C *u=q[i];
        if(u->t!=NULL)
            u->t->m+=u->m;
        for(int j=0;j<u->e;++j)
            a[u->d[j]]=u->m;
    }
}
int main() {
    freopen("ahocorasick.in","r",stdin),freopen("ahocorasick.out","w",stdout),scanf("%s",x),scanf("%d",&n),t=V();
    for(i=1;i<=n;++i)
        scanf("%s",c),I(t,c,i);
    for(B(t),p=t,g=strlen(x),i=0;i<g;++i) {
        for(;!p->f[x[i]-'a']&&p!=t;p=p->t);
        if(p->f[x[i]-'a']!=NULL)
            p=p->f[x[i]-'a'];
        ++p->m;
    }
    for(A(t),i=1;i<=n;++i)
        printf("%d\n",a[i]);
}