Cod sursa(job #2738012)

Utilizator stefantagaTaga Stefan stefantaga Data 5 aprilie 2021 13:32:37
Problema Aho-Corasick Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.14 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("ahocorasick.in");
ofstream g("ahocorasick.out");
struct trie
{
    int n0;
    vector <int> indici;
    trie *v[27],*fail;
    trie ()
    {
        n0=0;
        fail=0;
        indici.clear();
        for (int j=0;j<=26;j++)
        {
            v[j]=nullptr;
        }
    }
}*t,*q[100005];
int qe;
void insereaza(trie *tree,char *t,int indice)
{
    if (!*t)
    {
        tree->indici.push_back(indice);
        return;
    }
    int loc=*t-'a';
    if (tree->v[loc]==nullptr)
    {
        tree->v[loc]=new trie();
    }
    insereaza(tree->v[loc],t+1,indice);
}
void bfs ()
{
    t->fail= t;
    q[++qe]=t;
    for (int i=1;i<=qe;i++)
    {
        trie *crt=q[i];
        for (int j=0;j<=26;j++)
        {
            if (crt->v[j]!=nullptr)
            {
                trie *fiu=crt->fail;
                while (fiu!=t&&fiu->v[j]==nullptr)
                {
                    fiu=fiu->fail;
                }
                if (fiu->v[j]&&fiu->v[j]!=crt->v[j])
                {
                    fiu=fiu->v[j];
                }
                crt->v[j]->fail=fiu;
                q[++qe]=crt->v[j];
            }
        }
    }
    t->fail=0;
}
char s[1000005],s1[10005];
int n,i;
int n1;
void kmp()
{
    trie *p=t;
    n1=strlen(s);
    for (int i=0;i<n1;i++)
    {
        int lit=s[i]-'a';
        while (!p->v[lit]&&p!=t)
        {
            p=p->fail;
        }
        if (p->v[lit])
        {
            p=p->v[lit];
        }
        p->n0++;
    }
}
int sol[105];
void antibfs()
{
    while (qe)
    {
        trie *crt=q[qe];
        qe--;
        if (crt->fail)
        {
            crt->fail->n0+=crt->n0;
        }
        for (int j=0;j<crt->indici.size();j++)
        {
            sol[crt->indici[j]]=crt->n0;
        }
    }
}
int main()
{
    f>>s;
    f>>n;
    t=new trie();
    for (i=1;i<=n;i++)
    {
        f>>s1;
        insereaza(t,s1,i);
    }
    bfs();
    kmp();
    antibfs();
    for (i=1;i<=n;i++)
    {
        g<<sol[i]<<'\n';
    }
    return 0;
}