Cod sursa(job #2446767)

Utilizator ApostolIlieDanielApostol Daniel ApostolIlieDaniel Data 10 august 2019 18:09:29
Problema Aho-Corasick Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.66 kb
#include <bits/stdc++.h>

using namespace std;

const int ALPHA = 26, L = 2e4;

#define pb push_back

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

string t, s[1 + N];

class Ahoi {
    public :
        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 (L, 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;
}