Cod sursa(job #2591373)

Utilizator ezioconnorVlad - Gabriel Iftimescu ezioconnor Data 30 martie 2020 13:27:56
Problema Aho-Corasick Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.8 kb
#include <bits/stdc++.h>

#define fiu f[*s - 'a']

using namespace std;

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

int n;
char A[1000001], s[10001];

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

trie *root = new trie(), *rez[101], *aux, *nod;
queue <trie*> q;

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

inline 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() {
    in >> A >> n;
    for (int i = 1; i <= n; ++i) {
        in >> s;
        rez[i] = inserare(root, s);
    }
    q.push(root);
    while (!q.empty()) {
        nod = q.front();
        q.pop();
        for (int i = 0; i < 26; ++i) {
            if (nod->f[i]) {
                aux = nod->back;
                while (aux && aux->f[i] == NULL)
                    aux = aux->back;
                if (!aux)
                    nod->f[i]->back = root;
                else
                    nod->f[i]->back = aux->f[i];
                nod->f[i]->back->v.push_back(nod->f[i]);
                q.push(nod->f[i]);
            }
        }
    }
    aux = root;
    for (int i = 0; A[i]; ++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 (int i = 1; i <= n; ++i)
        out << rez[i]->sol << '\n';
    return 0;
}