Cod sursa(job #2591393)

Utilizator ezioconnorVlad - Gabriel Iftimescu ezioconnor Data 30 martie 2020 13:50:32
Problema Aho-Corasick Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.88 kb
#include <cstdio>
#include <vector>
#include <queue>
#define fiu f[*s-'a']

using namespace std;

FILE *fin = fopen("ahocorasick.in", "r");
FILE *fout = fopen("ahocorasick.out", "w");

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)
    {
        trie *vecin = nod->v[i]; dfs(vecin);
        nod->sol += vecin->sol;
    }
}

int main()
{
    fscanf(fin, "%s", &A); fscanf(fin, "%d", &n);
    for (i=1; i<=n; ++i)
    {
        fscanf(fin, "%s", &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)
        fprintf(fout, "%d\n", w[i]->sol);
    return 0;
}