Pagini recente » Cod sursa (job #3209254) | Cod sursa (job #2136180) | Cod sursa (job #2749858) | Cod sursa (job #2398435) | Cod sursa (job #1727406)
#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]);
}
}