Cod sursa(job #2197905)

Utilizator mihail.jianuJianu Mihail mihail.jianu Data 23 aprilie 2018 04:36:19
Problema Aho-Corasick Scor 95
Compilator cpp Status done
Runda Arhiva educationala Marime 2.7 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;
    vector<int>print;
    bool root;

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

    void add(int where, char s[], unsigned int p) {
        if (s[p] == NULL) {
            print.push_back(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();
        for (int i = 0; i < S; i++) {
            Trie* son = node->v[i];
            if (son != NULL) {
                q.push(son);
                if (node->root) {
                    son->fail = node;
                    continue;
                }
                Trie* curr = node->fail;
                while (!curr->root && curr->v[i] == NULL) {
                    curr = curr->fail;
                }
                if(curr->v[i] != NULL) {
                    son->fail = curr->v[i];
                }
                else {
                    son->fail = curr;
                }
                if (son->fail->print.size() > 0) {
                    son->dict = son->fail;
                }
                else {
                    son->dict = son->fail->dict;
                }
            }
        }
    }
}

Trie* T = new Trie(true);
const int MAX = 1e6;
int ans[N + 1];
char text[MAX + 1];
int n;

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

void solve() {
    Trie* curr = T;
    for (unsigned int i = 0; text[i]; 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);
}
const int L = 1e4;
char s[L + 1];

int main() {
    init();
    gets(text);
    scanf("%d\n",&n);
    for (int i = 0; i < n; i++) {
        gets(s);
        T->add(i, s, 0);
    }
    q.push(T);
    bfs(T);
    solve();
    for (int i = 0; i < n; i++) {
        cout << ans[i] << '\n';
    }
    return 0;
}