Cod sursa(job #2446723)

Utilizator ApostolIlieDanielApostol Daniel ApostolIlieDaniel Data 10 august 2019 16:13:32
Problema Aho-Corasick Scor 25
Compilator cpp-32 Status done
Runda Arhiva educationala Marime 2.43 kb
#include <bits/stdc++.h>

using namespace std;

const int ALPHA = 26;

#define pb push_back

struct Node {
    int nxt[ALPHA];
    int val;
    int fail;
};
const int N = 100;

string t, s[1 + N];

struct Ahoi {
    vector <Node> trie;
    vector <int> f;
    int cnt;
    Ahoi (int l, int n) {
        trie.resize (1 + l);
        f.resize (1 + n);
        cnt = 0;
    }
    void ins (int node, int ind, int p) {
        if (p == s[ind].size()) {
            f[ind] = node;
            return;
        }
        if (!trie[node].nxt[s[ind][p] - 'a'])
            trie[node].nxt[s[ind][p] - 'a'] = ++cnt;
        ins (trie[node].nxt[s[ind][p] - 'a'], ind, p + 1);
    }
    vector <int> ord;
    void fail () {
        queue <int> q;
        for (int i = 0; i < ALPHA; i++)
            if (trie[0].nxt[i])
                q.push (trie[0].nxt[i]);
        while (!q.empty ()) {
            int node = q.front ();
            q.pop ();
            ord.pb (node);
            for (int i = 0; i < ALPHA; i++)
                if (trie[node].nxt[i]) {
                    int vec = trie[node].nxt[i];
                    q.push (vec);
                    trie[vec].fail = trie[node].fail;
                    while (trie[vec].fail && !trie[trie[vec].fail].nxt[i])
                        trie[vec].fail = trie[trie[vec].fail].fail;
                    if (trie[trie[vec].fail].nxt[i])
                        trie[vec].fail = trie[trie[vec].fail].nxt[i];
                }
        }
    }
    void get_val () {
        int node = 0;
        for (int i = 0; i < t.size (); i++){
            while (node && !trie[node].nxt[t[i] - 'a'])
                node = trie[node].fail;
            if (trie[node].nxt[t[i] - 'a'])
                node = trie[node].nxt[t[i]-'a'];
            trie[node].val++;
        }
    }
    void prop () {
        reverse (ord.begin (), ord.end ());
        for (auto node : ord)
            trie[trie[node].fail].val += trie[node].val;
    }
};

int main() {
    int n;
    freopen ("ahocorasick.in", "r", stdin);
    freopen ("ahocorasick.out", "w", stdout);
    cin >> t;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> s[i];

    Ahoi dic (t.size (), n);
    for (int i = 1; i <= n; i++)
        dic.ins (0, i, 0);
    dic.fail (); dic.get_val (); dic.prop ();

    for (int i = 1; i <= n; i++)
        cout << dic.trie[dic.f[i]].val << "\n";
    return 0;
}