Pagini recente » Cod sursa (job #2310949) | Cod sursa (job #1370549) | Cod sursa (job #1951551) | Cod sursa (job #1308613) | Cod sursa (job #1947992)
/**
* 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;
}