Cod sursa(job #2591391)

Utilizator ezioconnorVlad - Gabriel Iftimescu ezioconnor Data 30 martie 2020 13:47:36
Problema Aho-Corasick Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.9 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;
}