Cod sursa(job #2927728)

Utilizator valentinchipuc123Valentin Chipuc valentinchipuc123 Data 21 octombrie 2022 11:03:09
Problema Aho-Corasick Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.54 kb
#include <bits/stdc++.h>
#define Aho_Corasick AC
using namespace std;

ifstream f("ahocorasick.in");
ofstream g("ahocorasick.out");

const int DIM=10005,Alphabet=26;
int n,hmax=0,Answer[DIM/100+1];
char txt[100*DIM],c[DIM];

struct Aho_Corasick
{
    vector<int>nodes;
    int n0;
    Aho_Corasick *Edge[Alphabet],*Fail;
    Aho_Corasick()
    {
        n0=0;
        Fail=NULL;
        memset(Edge,NULL,sizeof(Edge));
    }
}  *r;

void Insert(AC *Node,char *p,int i)
{
    if(!isalpha(*p))
    {
        Node->nodes.push_back(i);
        return;
    }
    int nxt=*p-'a';
    if(Node->Edge[nxt]==NULL) Node->Edge[nxt]=new AC;
    Insert(Node->Edge[nxt],p+1,i);
}

void Bfs(AC *Root)
{
    AC *Auxiliary;
    Root->Fail=Root;

    queue<AC*>q;
    q.push(Root);
    while(!q.empty())
    {
        AC *Node = q.front();
        q.pop();

        for(int i=0; i<Alphabet; i++)
            if(Node->Edge[i]!=NULL)
            {
                for(Auxiliary=Node->Fail; Auxiliary!=Root && Auxiliary->Edge[i]==NULL; Auxiliary=Auxiliary->Fail);
                if(Auxiliary->Edge[i]!=NULL && Auxiliary->Edge[i]!=Node->Edge[i]) Auxiliary=Auxiliary->Edge[i];

                Node->Edge[i]->Fail=Auxiliary;
                q.push(Node->Edge[i]);
            }
    }
    Root->Fail=NULL;
}

void Bfss(AC *Root)
{
    queue< pair<AC*,int> >q;
    vector< AC* > levels[hmax+1] ;
    q.push({Root,0});

    while(!q.empty())
    {
        AC *Node = q.front().first;
        int h=q.front().second;
        levels[h].push_back(Node);
        q.pop();

        for(int i=0; i<Alphabet; i++)
        {
            if(Node->Edge[i]!=NULL)
            {
                q.push({Node->Edge[i],h+1});
            }
        }
    }

    for(int i=hmax; i>=1; i--)
    {
        for(int j=0; j<levels[i].size(); j++)
        {
            AC* Node = levels[i][j];
            Node->Fail->n0 += Node->n0;
            for(int z=0; z<Node->nodes.size(); z++) Answer[Node->nodes[z]]=Node->n0;
        }
    }
}

int main()
{
    f>>txt;
    f>>n;
    r=new Aho_Corasick;

    for(int i=1; i<=n; i++)
    {
        f>>c;
        hmax=max(hmax,(int)strlen(c));
        Insert(r,c,i);
    }
    Bfs(r);

    AC* p = r;
    int l=strlen(txt);
    for(int i=0; i<l; i++)
    {
        int nxt=txt[i]-'a';
        for(; p->Edge[nxt]==NULL&&p!=r; p=p->Fail);
        if(p->Edge[nxt]!=NULL) p=p->Edge[nxt];
        ++p->n0;
    }
    Bfss(r);
    for(int i=1; i<=n; i++) g<<Answer[i]<<'\n';
    return 0;
}