Cod sursa(job #2197902)

Utilizator mihail.jianuJianu Mihail mihail.jianu Data 23 aprilie 2018 04:10:46
Problema Aho-Corasick Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 2.82 kb
#include <bits/stdc++.h>

using namespace std;

const int S = 'z' + 1 - 'a';
const int N = 100;

class Trie;

queue<Trie*> q;

class Trie {
public:
    Trie* v[S];
    Trie* fail;
    Trie* dict;
    int print;
    bool root;

    Trie(bool f) {
        print = -1;
        root = f;
        fail = NULL;
        dict = NULL;
        for (int i = 0; i < S; i++)
            v[i] = NULL;
        if (f) {
            fail = this;
        }
    }

    void add(int where, string &s, unsigned int p) {
        if (s.size() == p) {
            print = where;
            return;
        }
        if (v[s[p] - 'a'] == NULL) {
            v[s[p] - 'a'] = new Trie(false);
        }
        v[s[p] - 'a']->add(where, s, p + 1);
    }
};

void bfs (Trie* trie) {
    q.push(trie);
    while (!q.empty()) {
        Trie* node = q.front();
        q.pop();
        if (node->root) {
            for (int i = 0; i < S; i++) {
                if(node->v[i] != NULL) {
                    node->v[i]->fail = node;
                    q.push(node->v[i]);
                }
            }
            continue;
        }
        for (int i = 0; i < S; i++) {
            if (node->v[i] != NULL) {
                q.push(node->v[i]);
                Trie* curr = node->fail;
                while (!curr->root && curr->v[i] == NULL) {
                    curr = curr->fail;
                }
                if(curr->v[i] != NULL) {
                    node->v[i]->fail = curr->v[i];
                }
                else {
                    node->v[i]->fail = curr;
                }
                if (node->v[i]->fail->print >= 0) {
                    node->v[i]->dict = node->v[i]->fail;
                }
                else {
                    node->v[i]->dict = node->v[i]->fail->dict;
                }
            }
        }
    }
}

Trie* T = new Trie(true);
string read[N + 1];
int ans[N + 1];
string text;
int n;

void update_ans(Trie* trie) {
    if(trie == NULL)
        return;
    if (trie->print >= 0)
        ans[trie->print]++;
    update_ans(trie->dict);
}

void solve() {
    Trie* curr = T;
    for (unsigned int i = 0; i < text.size(); i++) {
        int c = text[i]- 'a';
        while (!curr->root && curr->v[c] == NULL) {
            curr = curr->fail;
        }
        if (curr->v[c] != NULL)
            curr = curr->v[c];
        update_ans(curr);
    }
}

void init() {
    freopen("ahocorasick.in", "r", stdin);
    freopen("ahocorasick.out", "w", stdout);
}

int main() {
    init();
    cin >> text >> n;
    for (int i = 0; i < n; i++) {
        cin >> read[i];
        T->add(i, read[i], 0);
    }
    q.push(T);
    bfs(T);
    solve();
    for (int i = 0; i < n; i++) {
        cout << ans[i] << '\n';
    }
    return 0;
}