Pagini recente » Cod sursa (job #2648000) | Istoria paginii runda/oni2011_9_2/clasament | Cod sursa (job #2332865) | Cod sursa (job #1571228) | Cod sursa (job #1568442)
/* 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;
}