Cod sursa(job #2187592)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 26 martie 2018 17:04:11
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.35 kb
#include <bits/stdc++.h>

using namespace std;

const int sigma = 26;
const int nmax = 100 + 10;
string s_to_update;

struct trie {
    int cnt;
    trie *phi;
    trie *son[sigma];

    trie() {
        cnt = 0; phi = NULL;
        for (int i = 0; i < sigma; ++i)
            son[i] = NULL;
    }

    trie *update(int pos) {
        if (pos == s_to_update.size()) {
            return this;
        }

        int to = s_to_update[pos] - 'a';
        if (son[to] == NULL)
            son[to] = new trie;

        return son[to] -> update(pos + 1);
    }
};

trie *whr[nmax];

class aho_corasick {
    trie *root = new trie;
    int dmax = 10, dim = 0;
    trie **q;

public:
    void add(string s, int idx) {
        s_to_update = s;
        dmax += s.size();
        whr[idx] = root -> update(0);
    }

    void compute_phi() {
        q = new trie *[dmax];

        q[++dim] = root; root -> phi = root;
        for (int i = 1; i <= dim; ++i) {
            trie *node = q[i];

            for (int to = 0; to < sigma; ++to) {
                if (node -> son[to] == NULL)
                    continue;

                trie *k = node -> phi;
                while (k != root && k -> son[to] == NULL)
                    k = k -> phi;
                if (k != node && k -> son[to] != NULL)
                    k = k -> son[to];

                node -> son[to] -> phi = k;
                q[++dim] = node -> son[to];
            }
        }
    }

    void compute_ans(string S) {
        trie *k = root;
        for (int i = 0; i < S.size(); ++i) {
            int to = S[i] - 'a';

            while (k != root && k -> son[to] == NULL)
                k = k -> phi;
            if (k -> son[to] != NULL)
                k = k -> son[to];

            k -> cnt++;
        }

        for (int i = dim; i; --i)
            q[i] -> phi -> cnt += q[i] -> cnt;
    }
};

string str, s;
int n;

aho_corasick ac;

int main() {
    freopen("ahocorasick.in","r",stdin);
    freopen("ahocorasick.out","w",stdout);

    ios_base :: sync_with_stdio(false);

    cin >> str;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> s;
        ac.add(s, i);
    }

    ac.compute_phi();
    ac.compute_ans(str);
    for (int i = 1; i <= n; ++i)
        cout << whr[i] -> cnt << '\n';

    return 0;
}