Cod sursa(job #2776260)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 19 septembrie 2021 09:53:27
Problema Aho-Corasick Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include<fstream>
#include<cstring>
using namespace std;
ifstream F("ahocorasick.in");
ofstream G("ahocorasick.out");
int g,n,l,f[10005],j,s,i,u;
char x[1000005],c[10005];
typedef struct A {
    int n,d[105],e;
    struct A *f[26],*h;
}C;
C *q[100100025],*t,*p;
C *V()
{
    C *r=new C;
    r->n=0,r->h=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;
    }
    int u=*p-'a';
    if(!t->f[u])
        t->f[u]=V();
    I(t->f[u],p+1,i);
}
void B(C *t)
{
    C *d;
    t->h=t;
    for(q[j=s=1]=t;j<=s;++j) {
        C *r=q[j];
        for(int i=0;i<26;++i)
            if(r->f[i]) {
                for(d=r->h;d!=t&&!d->f[i];d=d->h);
                if(d->f[i]&&d->f[i]!=r->f[i])
                    d=d->f[i];
                r->f[i]->h=d,q[++s]=r->f[i];
            }
    }
    t->h=NULL;
}
void D(C *t)
{
    int i,k;
    for(i=s;i;--i) {
        C *r=q[i];
        if(r->h)
            r->h->n+=r->n;
        for(k=0;k<r->e;++k)
            f[r->d[k]]=r->n;
    }
}
int main()
{
    F>>x>>n,t=V();
    for(i=1;i<=n;++i)
        F>>c,I(t,c,i);
    B(t),p=t,g=strlen(x);
    for(i=0;i<g;++i) {
        u=x[i]-'a';
        for(;!p->f[u]&&p!=t;p=p->h);
        if(p->f[u])
            p=p->f[u];
        ++p->n;
    }
    D(t);
    for(i=1;i<=n;++i)
        G<<f[i]<<"\n";
    return 0;
}