Cod sursa(job #2591388)

Utilizator ezioconnorVlad - Gabriel Iftimescu ezioconnor Data 30 martie 2020 13:39:31
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 *in = fopen("ahocorasick.in", "r");
FILE *out = fopen("ahocorasick.out", "w");

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);
}

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