Cod sursa(job #1947992)

Utilizator andrei.arnautuAndi Arnautu andrei.arnautu Data 31 martie 2017 16:31:45
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.49 kb
/**
  *  Worg
  */
#include <queue>
#include <cstdio>
#include <vector>
#include <algorithm>

using std::queue;
using std::vector;
FILE *fin = freopen("ahocorasick.in", "r", stdin);
FILE *fout = freopen("ahocorasick.out", "w", stdout);

const int kMaxTextLen = 1 + 1000000;
const int kMaxWordLen = 1 + 10000;
const int kMaxN = 1 + 100;
const int sigma = 26;

/*-------- Structures --------*/
struct Trie {
    Trie *son[sigma];
    Trie *fail_link;

    vector<int > word_list;
    int count;

    Trie() {
        for(int i = 0; i < sigma; i++) {
            son[i] = NULL;
        }
        fail_link = NULL;
        count = 0;
    }
};
/*-------- Input data --------*/
int N;
char text[kMaxTextLen];
char word[kMaxWordLen];
/*-------- Algorithm data --------*/
Trie *root = new Trie();

queue<Trie* > my_queue;
vector<Trie* > node_list;

int query_answer[kMaxN];
/*-------- --------*/

void Insert(Trie *node, char *cursor, int word_id) {
    if(*cursor == NULL) {
        node->word_list.push_back(word_id);
    } else {
        if(node->son[*cursor - 'a'] == NULL) {
            node->son[*cursor - 'a'] = new Trie();
        }
        Insert(node->son[*cursor - 'a'], cursor + 1, word_id);
    }
}

void ReadInput() {
    scanf("%s", text);
    scanf("%d", &N);
    for(int i = 1; i <= N; i++) {
        scanf("%s", word);
        Insert(root, word, i);
    }
}

void ComputeFailLinks() {
    root->fail_link = root;
    for(int i = 0; i < sigma; i++) {
        if(root->son[i] != NULL) {
            root->son[i]->fail_link = root;
            my_queue.push(root->son[i]);
        }
    }

    while(!my_queue.empty()) {
        Trie *node = my_queue.front(); my_queue.pop();
        //  Calculam fail_linkurile pentru toti fii lui node
        for(int i = 0; i < sigma; i++) {
            if(node->son[i] != NULL) {
                Trie *fail_node = node->fail_link;
                while(fail_node != root && fail_node->son[i] == NULL) {
                    fail_node = fail_node->fail_link;
                }

                if(fail_node->son[i] != NULL && fail_node->son[i] != node->son[i]) {
                    fail_node = fail_node->son[i];
                }
                node->son[i]->fail_link = fail_node;
                my_queue.push(node->son[i]);
            }
        }
    }
}

void FindAppearances(char *cursor) {
    Trie *node = root;
    while(*cursor != '\0') {
        while(node != root && node->son[*cursor - 'a'] == NULL) {
            node = node->fail_link;
        }
        if(node->son[*cursor - 'a'] != NULL) {
            node = node->son[*cursor - 'a'];
        }
        node->count ++;
        cursor ++;
    }

    my_queue.push(root);
    while(!my_queue.empty()) {
        Trie *node = my_queue.front(); my_queue.pop();
        node_list.push_back(node);

        for(int i = 0; i < sigma; i++) {
            if(node->son[i] != NULL) {
                my_queue.push(node->son[i]);
            }
        }
    }

    std::reverse(node_list.begin(), node_list.end());
    for(auto node : node_list) {
        node->fail_link->count += node->count;
        for(auto word_id : node->word_list) {
            query_answer[word_id] += node->count;
        }
    }
}

void WriteOutput() {
    for(int i = 1; i <= N; i++) {
        printf("%d\n", query_answer[i]);
    }
}

int main() {
    ReadInput();
    ComputeFailLinks();
    FindAppearances(text);
    WriteOutput();
    return 0;
}