Cod sursa(job #1727406)

Utilizator FlameingoAiordachioaei Marius Flameingo Data 10 iulie 2016 18:31:36
Problema Aho-Corasick Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 3.06 kb

#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <queue>
#include <stack>

#define ALPHA_LEN 27
#define AMAX 1000003
#define WMAX 10003
#define NMAX 103

using namespace std;

typedef struct TrieNode TrieNode;
struct TrieNode {

    TrieNode* children[ALPHA_LEN];
    TrieNode* fail;
    int word_index;
    int apperances;

    TrieNode () {
        memset(children, 0, sizeof(TrieNode*) * ALPHA_LEN);
        fail = NULL;
        word_index = apperances = 0;
    }

};

void insert_into_trie (TrieNode *root, char string[], int word_index) {

    int i,
        string_len = strlen(string);

    TrieNode *cursor = root;

    for (i = 0; i < string_len; ++i) {
        if (cursor->children[string[i] - 'a'] == NULL) {
            cursor->children[string[i] - 'a'] = new TrieNode();
        }
        cursor = cursor->children[string[i] - 'a'];
    }

    cursor->word_index = word_index;

}

queue <TrieNode*> Q;
stack <TrieNode*> reverse_bfs;
TrieNode *root;

void create_fail_links () {

    int i;

    TrieNode* current_node;

    root->fail = NULL;
    for (i = 0; i < ALPHA_LEN; ++i) {
        if (root->children[i] != NULL) {
            root->children[i]->fail = root;
            Q.push(root->children[i]);
        }
    }

    while (!Q.empty()) {
        current_node = Q.front();
        Q.pop();

        reverse_bfs.push(current_node);

        for (i = 0; i < ALPHA_LEN; ++i) {
            if (current_node->children[i] != NULL) {
                TrieNode *fail = current_node->fail;
                while (fail != NULL) {
                    if (fail->children[i] != NULL) {
                        current_node->children[i]->fail = fail->children[i];
                        break;
                    }
                    fail = fail->fail;
                }
                if (fail == NULL) {
                    current_node->children[i]->fail = root;
                }
                Q.push(current_node->children[i]);
            }
        }
    }

}

char text[AMAX];
char words[NMAX][WMAX];
int ans[NMAX];

int main () {

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

    int N, i;

    scanf ("%s", text);
    scanf ("%d", &N);

    root = new TrieNode();

    for (i = 1; i <= N; ++i) {
        scanf ("%s", words[i]);
        insert_into_trie (root, words[i], i);
    }

    create_fail_links();

    int text_len = strlen(text);
    TrieNode *cursor = root;
    for (i = 0; i < text_len; ++i) {
        while (cursor != NULL && cursor->children[text[i] - 'a'] == NULL) {
            cursor = cursor->fail;
        }
        if (cursor != NULL) {
            cursor = cursor->children[text[i] - 'a'];
        }
        else {
            cursor = root;
        }
        ++cursor->apperances;
    }

    while (!reverse_bfs.empty()) {
        cursor = reverse_bfs.top();
        reverse_bfs.pop();

        ans[cursor->word_index] = cursor->apperances;
        if (cursor->fail != NULL) {
            cursor->fail->apperances += cursor->apperances;
        }
    }

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

}