Cod sursa(job #2104000)

Utilizator patcasrarespatcas rares danut patcasrares Data 11 ianuarie 2018 00:13:22
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.76 kb
#include<fstream>
#include<iostream>
#include<algorithm>
#include<bitset>
#include<cmath>
#include<cstring>
#include<vector>
#include<map>
#define pb push_back
#define DN 10005
#define DL 1000005
using namespace std;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
int n,cd,l,r[DN];
char c[DL],tx[DL];
struct ac
{
    vector<int>v;
    ac *fail=0,*f[30]={0};
    int nr=0;
}*q[DN*105];
ac *t=new ac;
ac *p=new ac;
void inserare(ac *nod,char *c,int i)
{
    if(*c==0)
    {
        nod->v.pb(i);
        return;
    }
    if(nod->f[*c-'a']==0)
        nod->f[*c-'a']=new ac;
    inserare(nod->f[*c-'a'],c+1,i);
}
void bfs()
{
    ac *nod,*d;
    t->fail=t;
    cd=1;
    q[1]=t;
    for(int i=1;i<=cd;i++)
    {
        nod=q[i];
        for(int j=0;j<30;j++)
            if(nod->f[j]!=0)
            {
                for(d=nod->fail;d!=t&&d->f[j]==0;d=d->fail);
                if(d->f[j]!=0&&d->f[j]!=nod->f[j])
                    d=d->f[j];
                nod->f[j]->fail=d;
                cd++;
                q[cd]=nod->f[j];
            }
    }
    t->fail=0;
}
void antibfs()
{
    ac *nod;
    for(int i=cd;i>=1;i--)
    {
        nod=q[i];
        if(nod->fail!=0)
            nod->fail->nr+=nod->nr;
        for(int j=0;j<nod->v.size();j++)
            r[nod->v[j]]=nod->nr;
    }
}
int main()
{
    fin>>tx;
    fin>>n;
    for(int i=1;i<=n;i++)
    {
        fin>>c;
        inserare(t,c,i);
    }
    bfs();
    l=strlen(tx);
    p=t;
    for(int i=0;i<l;i++)
    {
        int urm=tx[i]-'a';
        for(;p->f[urm]==0&&p!=t;p=p->fail);
        if(p->f[urm]!=0)
            p=p->f[urm];
        p->nr++;
    }
    antibfs();
    for(int i=1;i<=n;i++)
        fout<<r[i]<<'\n';
}