Cod sursa(job #1757484)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 15 septembrie 2016 10:16:44
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.15 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>

using namespace std;

ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");

int n;
char a[1000005], word[10005];

struct Trie {

    int count;
    Trie *sons[26], *back;
    vector<Trie*> adj;

    Trie() {
        count = 0;
        for (int i = 0; i < 26; ++i)
            sons[i] = NULL;
        back = NULL;
        adj.clear();
    }

} *root = new Trie, *res[105];

Trie *updateTrie(Trie *node, char *s) {

    if (*s == 0)
        return node;

    if (node->sons[*s - 'a'] == NULL)
        node->sons[*s - 'a'] = new Trie;

    return updateTrie(node->sons[*s - 'a'], s + 1);

}

void bfs(void) {

    queue<Trie*> que;
    que.push(root);

    while (!que.empty()) {

        Trie *node = que.front();

        for (int i = 0; i < 26; ++i) {

            if (node->sons[i] == NULL)
                continue;

            Trie *aux = node->back;

            while (aux && !aux->sons[i])
                aux = aux->back;

            if (!aux)
                aux = root;
            else
                aux = aux->sons[i];

            node->sons[i]->back = aux;
            aux->adj.push_back(node->sons[i]);

            que.push(node->sons[i]);

        }

        que.pop();

    }

}

void dfs(Trie *node) {

    for (vector<Trie*>::iterator adj = node->adj.begin(); adj != node->adj.end(); ++adj) {

        dfs(*adj);
        node->count += (*adj)->count;

    }

}

int main() {

    fin >> a;
    fin >> n;

    for (int i = 1; i <= n; ++i) {

        fin >> word;
        res[i] = updateTrie(root, word);

    }

    bfs();

    Trie *curr = root;
    for (char *pch = a; *pch; ++pch) {

        while (curr && !curr->sons[*pch - 'a'])
            curr = curr->back;

        if (curr == NULL)
            curr = root;
        else
            curr = curr->sons[*pch - 'a'];

        curr->count++;

    }

    dfs(root);

    for (int i = 1; i <= n; ++i)
        fout << res[i]->count << '\n';

    return 0;

}

//Trust me, I'm the Doctor!