Cod sursa(job #1568442)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 14 ianuarie 2016 11:39:02
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 6.4 kb
/*                  State Machine using C++ classes, made by 'EmanuelNrx'
 *
 *  Require: <deque> & <vector>
 *
 *  Functions: - insert_word // insert a word into the state machine
 *             - delete_word // delete a word from the state machine
 *             - count_word // count the aparitions of the word in the state machine
 *             - longest_prefix // returns the length of the longest prefix of the word with the words in the state machine
 *             - build_occurrences // build the occurrences of the words in the state machine in a text
 *             - count_occurrences // returns the number of occurrences of the word int the last text inserted
 */

#include <cstdio>
#include <deque>
#include <vector>

const int SIGMA = 26;
const int DIM = 1 << 20;
using namespace std;

char String[DIM]; int NrWords;
char Word[111][DIM / 100];

class state_machine {
  private:

    struct trie {

        int cnt_words;
        int cnt_children;
        int cnt_occurrences;
        trie *back_node;
        trie *children[SIGMA];
        vector <trie *> front_node;

        trie () {

            cnt_words = NULL;
            cnt_children = NULL;
            cnt_occurrences = NULL;
            back_node = NULL;

            for( int i = 0; i < SIGMA; i ++ )
                children[i] = NULL;

            front_node.clear();
        }
    } *Root = new trie;

    void insert_word( trie *Node, char *String ) {

        if( *String == NULL ) {
            Node -> cnt_words ++;
            return;
        }

        if( Node -> children[*String - 'a'] == NULL ) {
            Node -> children[*String - 'a'] = new trie;
            Node -> cnt_children ++;
        }

        insert_word( Node -> children[*String - 'a'], String + 1 );
        return;
    }

    int delete_word( trie *Node, char *String ) {

        if( *String == NULL ) Node -> cnt_words --; else
        if( delete_word( Node -> children[*String - 'a'], String + 1 ) )
            Node -> cnt_children --;

        if( Node != Root && Node -> cnt_words == NULL && Node -> cnt_children == NULL ) {
            delete Node;
            return 1;
        }

        return 0;
    }

    int count_word( trie *Node, char *String ){

        if( *String == NULL )
            return Node -> cnt_words;

        if( Node -> children[*String - 'a'] != NULL )
            return count_word( Node -> children[*String - 'a'], String + 1 );

        return 0;
    }

    int longest_prefix( trie *Node, char *String, int prefix_length ) {

        if( *String == NULL )
            return prefix_length;

        if( Node -> children[*String - 'a'] != NULL )
            return longest_prefix( Node -> children[*String - 'a'], String + 1, prefix_length + 1 );

        return prefix_length;
    }

    void reset_machine( trie *Node ) {
        Node -> cnt_occurrences = NULL;
        Node -> back_node = NULL;
        Node -> front_node.clear();

        for( int i = 0; i < SIGMA; i ++ )
            if( Node -> children[i] != NULL )
                reset_machine( Node -> children[i] );

        return;
    }

    void build_back_edges( trie *start_node ) {

        deque <trie *> Queue;
        Queue.push_back( start_node );

        while( !Queue.empty() ) {
            trie *Node = Queue.front();

            for( int i = 0; i < SIGMA; i ++ ) {
                if( Node -> children[i] != NULL ) {
                    trie *aux_node = Node -> back_node;

                    while( aux_node && aux_node -> children[i] == NULL )
                        aux_node = aux_node -> back_node;

                    if( aux_node == NULL )
                        Node -> children[i] -> back_node = Root;
                    else
                        Node -> children[i] -> back_node = aux_node -> children[i];

                    Node -> children[i] -> back_node -> front_node.push_back( Node -> children[i] );
                    Queue.push_back( Node -> children[i] );
                }
            }

            Queue.pop_front();
        }

        return;
    }

    void build_occurrences( trie *aux_node, char *String ) {

        if( *String == NULL )
            return;

        while( aux_node != Root && aux_node -> children[*String - 'a'] == NULL )
            aux_node = aux_node -> back_node;

        if( aux_node -> children[*String - 'a'] != NULL )
            aux_node = aux_node -> children[*String - 'a'];

        aux_node -> cnt_occurrences ++;
        build_occurrences( aux_node, String + 1 );

        return;
    }

    void build_partial_sum( trie *Node ) {

        for( int i = 0; i < Node -> front_node.size(); i ++ ) {
            build_partial_sum( Node -> front_node[i] );
            Node -> cnt_occurrences += Node -> front_node[i] -> cnt_occurrences;
        }

        return;
    }

    int count_occurrences( trie *Node, char *String ) {

        if( *String == NULL )
            return Node -> cnt_occurrences;

        if( Node -> children[*String - 'a'] != NULL )
            return count_occurrences( Node -> children[*String - 'a'], String + 1 );

        return 0;
    }

  public:

    void insert_word( char *String ) {
        insert_word( Root, String );
        return;
    }

    void delete_word( char *String ) {
        delete_word( Root, String );
        return;
    }

    int count_word( char *String ) {
        return count_word( Root, String );
    }

    int longest_prefix( char *String ) {
        return longest_prefix( Root, String, 0 );
    }

    void build_occurrences( char *String ) {
        reset_machine( Root );
        build_back_edges( Root );
        build_occurrences( Root, String );
        build_partial_sum( Root );
        return;
    }

    int count_occurrences( char *String ) {
        return count_occurrences( Root, String );
    }

} my_state_machine;

int main () {

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

    scanf( "%s", String );
    scanf( "%d", &NrWords );

    for( int i = 1; i <= NrWords; i ++ ) {
        scanf( "%s", Word[i] );
        my_state_machine.insert_word( Word[i] );
    }

    my_state_machine.build_occurrences( String );

    for( int i = 1; i <= NrWords; i ++ )
        printf( "%d\n", my_state_machine.count_occurrences( Word[i] ));

    return 0;
}