Cod sursa(job #3357828)

Utilizator TestLicenta123Test Test TestLicenta123 Data 13 iunie 2026 15:22:46
Problema Aho-Corasick Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.35 kb
#include <vector>
#include <algorithm>
#include <queue>
#include <fstream>
using namespace std;

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

string S;
int n;
string s[110];

void citire() {
    cin >> S;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
    }
}

const int lit = 'z' - 'a' + 1;

struct nod {
    int nxt[lit], fail, val;
    nod() {
        for (int i = 0; i < lit; i++) nxt[i] = 0;
        fail = 0;
        val = 0;
    }
} v[1000100];
int pnt = 0;
int fin[110];

void trie(int nod, int sir, int lv) {
    if (lv == (int)s[sir].size()) {
        fin[sir] = nod;
        return;
    }
    int c = s[sir][lv] - 'a';
    if (!v[nod].nxt[c]) {
        v[nod].nxt[c] = ++pnt;
    }
    trie(v[nod].nxt[c], sir, lv + 1);
}

queue<int> q;

void fail() {
    for (int i = 0; i < lit; i++) {
        if (v[0].nxt[i]) {
            v[v[0].nxt[i]].fail = 0;
            q.push(v[0].nxt[i]);
        }
    }
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        for (int i = 0; i < lit; i++) {
            if (v[now].nxt[i]) {
                int child = v[now].nxt[i];
                int f = v[now].fail;
                while (f && !v[f].nxt[i]) {
                    f = v[f].fail;
                }
                if (v[f].nxt[i]) {
                    f = v[f].nxt[i];
                }
                v[child].fail = f;
                q.push(child);
            }
        }
    }
}

void val() {
    int now = 0;
    for (int i = 0; i < (int)S.size(); i++) {
        int c = S[i] - 'a';
        while (now && !v[now].nxt[c]) {
            now = v[now].fail;
        }
        if (v[now].nxt[c]) {
            now = v[now].nxt[c];
        }
        v[now].val++;
    }
}

void prop() {
    vector<int> ord;
    q.push(0);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        ord.push_back(u);
        for (int i = 0; i < lit; i++) {
            if (v[u].nxt[i]) {
                q.push(v[u].nxt[i]);
            }
        }
    }
    reverse(ord.begin(), ord.end());
    for (int u : ord) {
        if (v[u].fail) {
            v[v[u].fail].val += v[u].val;
        }
    }
}

int main() {
    citire();
    for (int i = 1; i <= n; i++) {
        trie(0, i, 0);
    }
    fail();
    val();
    prop();
    for (int i = 1; i <= n; i++) {
        cout << v[fin[i]].val << '\n';
    }
    return 0;
}