Cod sursa(job #3226108)

Utilizator juniorOvidiu Rosca junior Data 20 aprilie 2024 08:42:37
Problema Aho-Corasick Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.49 kb
// Incercare fara pointeri.

#include <cstdio>
#include <cstring>
#include <cctype>
#include <vector>
#define DL 1000005
#define DN 10005
#define DA 26 // dimensiunea alfabetului
using namespace std;

int lg, n, final[DN];
char tx[DL], c[DN];

struct ac {
    vector<int> nd; // sirurile care se termina in nodul curent
    int n0; // numarul de potriviri din nodul curent sau din fii lui
    int f[DA], fail;
    ac() : n0(0), fail(0) {
        memset(f, -1, sizeof(f));
    }
};

vector<ac> trie(1);

void ins(int t, char *p, int i) {
    if (!isalpha(*p)) {
        trie[t].nd.push_back(i);
        return;
    }
    int urm = *p - 'a';
    if (trie[t].f[urm] == -1) {
        trie[t].f[urm] = trie.size();
        trie.emplace_back();
    }
    ins(trie[t].f[urm], p + 1, i);
}

void bfs() {
    vector<int> q;
    q.push_back(0); // începem de la rădăcină
    trie[0].fail = 0; // fail-ul rădăcinii este ea însăși
    int front = 0;
    while (front < q.size()) {
        int fr = q[front++];
        for (int i = 0; i < DA; ++i) {
            if (trie[fr].f[i] != -1) {
                int child = trie[fr].f[i];
                int fail = trie[fr].fail;
                while (fail != 0 && trie[fail].f[i] == -1)
                    fail = trie[fail].fail;
                if (trie[fail].f[i] != -1)
                    fail = trie[fail].f[i];
                trie[child].fail = fail;
                q.push_back(child);
            }
        }
    }
}

void process_text() {
    int p = 0;
    lg = strlen(tx);
    for (int i = 0; i < lg; ++i) {
        int urm = tx[i] - 'a';
        while (trie[p].f[urm] == -1 && p != 0)
            p = trie[p].fail;
        if (trie[p].f[urm] != -1)
            p = trie[p].f[urm];
        trie[p].n0++;
    }
}

void antibfs() {
    vector<int> q;
    for (int i = 0; i < trie.size(); ++i)
        q.push_back(i);
    for (int i = q.size() - 1; i >= 0; --i) {
        int fr = q[i];
        int fail = trie[fr].fail;
        trie[fail].n0 += trie[fr].n0;
        for (int idx : trie[fr].nd)
            final[idx] = trie[fr].n0;
    }
}

int main() {
    freopen("ahocorasick.in", "r", stdin);
    freopen("ahocorasick.out", "w", stdout);
    scanf("%s", tx);
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%s", c);
        ins(0, c, i);
    }
    bfs();
    process_text();
    antibfs();
    for (int i = 1; i <= n; ++i) printf("%d\n", final[i]);
    return 0;
}