Cod sursa(job #2523372)

Utilizator LeVladzCiuperceanu Vlad LeVladz Data 13 ianuarie 2020 23:03:33
Problema Aho-Corasick Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.8 kb
#include <fstream>
#include <vector>
#include <queue>
#define fiu f[*s-'a']

using namespace std;

ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");

int n,i;
char A[1000005],s[10005];

struct trie{
    int sol;
    trie *f[26];
    trie *back;
    vector<trie *> v;
    trie ()
    {
        sol = 0;
        for (int i=0; i<26; i++)
            f[i] = 0;
        back = 0;
        v.clear();
    }
};

trie *root = new trie();
trie *w[105],*nod,*aux;
queue<trie *> c;

trie *adauga(trie *r, char *s)
{
    if (*s == 0)
        return r;
    if (r->fiu == NULL)
        r->fiu = new trie;
    return adauga(r->fiu, s+1);
}

void dfs(trie *nod)
{
    for (int i=0; i<nod->v.size(); i++)
    {
        dfs(nod->v[i]);
        nod->sol += nod->v[i]->sol;
    }
}

int main()
{
    fin >> A >> n;
    for (i=1; i<=n; i++)
    {
        fin >> s;
        w[i] = adauga(root, s);
    }
    c.push(root);
    while (!c.empty())
    {
        nod = c.front(); c.pop();
        for (i=0; i<26; i++)
            if (nod->f[i])
            {
                aux = nod->back;
                while (aux && aux->f[i] == NULL)
                    aux = aux->back;
                if (aux == 0)
                    nod->f[i]->back = root;
                else
                    nod->f[i]->back = aux->f[i];
                nod->f[i]->back->v.push_back(nod->f[i]);
                c.push(nod->f[i]);
            }
    }
    aux = root;
    for (i=0; A[i]!=0; i++)
    {
        while (aux != root && aux->f[A[i]-'a'] == NULL)
            aux = aux->back;
        if (aux->f[A[i]-'a'] != NULL)
            aux = aux->f[A[i]-'a'];
        aux->sol++;
    }
    dfs(root);
    for (i=1; i<=n; i++)
        fout << w[i]->sol << "\n";
    return 0;
}