Pagini recente » Cod sursa (job #2654812) | Borderou de evaluare (job #1330669) | Cod sursa (job #3135443) | Cod sursa (job #3168227) | Cod sursa (job #2668574)
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
struct ahocor {
int matches;
vector<int> nd;
ahocor *sons[26], *fail;
ahocor() {
matches = 0;
fail = 0;
memset(sons, 0, sizeof(sons));
}
} *root, *q[100000003];
int q_len;
char a[1000003];
char current_word[10003];
int antibfs_res[103];
void insert_ahocor(ahocor *node, char * word, int wordno) {
if (*word < 'a' || *word > 'z') {
node->nd.push_back(wordno);
return;
}
int current_son =*word - 'a';
if(node->sons[current_son] == 0)
node->sons[current_son] = new ahocor;
insert_ahocor(node->sons[current_son], word+1, wordno);
}
void bfs(ahocor * start) {
ahocor *current_fail, *current_node;
start->fail = start;
int q_front = 1;
q_len = 1;
q[1] = start;
while (q_front <= q_len) {
current_node = q[q_front];
++q_front;
for(int i=0; i<26; ++i)
if (current_node->sons[i]) {
for(current_fail = current_node->fail; current_fail != start && current_fail->sons[i] == NULL; current_fail = current_fail->fail);
if (current_fail->sons[i] && current_fail->sons[i] != current_node->sons[i])
current_fail = current_fail->sons[i];
current_node->sons[i]->fail = current_fail;
++q_len;
q[q_len] = current_node->sons[i];
}
}
start->fail = 0;
}
void match_a() {
ahocor * current_node = root;
int current_son = 0;
for(int i=0; a[i]>='a'&&a[i] <='z'; ++i) {
current_son = a[i] - 'a';
for(;current_node->sons[current_son]==NULL && current_node != root; current_node = current_node->fail);
if (current_node->sons[current_son])
current_node = current_node->sons[current_son];
current_node->matches++;
}
}
void antibfs(ahocor * start) {
ahocor * current_node;
for(int i = q_len; i>=1; --i) {
current_node = q[i];
if (current_node->fail)
current_node->fail->matches += current_node->matches;
for(int j=0; j<current_node->nd.size(); ++j)
antibfs_res[current_node->nd[j]] = current_node->matches;
}
}
int main() {
ifstream in("ahocorasick.in");
ofstream out("ahocorasick.out");
in >> a;
int m;
root = new ahocor;
in >> m;
for(int i=1; i<=m; ++i) {
in >>current_word;
insert_ahocor(root, current_word, i);
}
bfs(root);
match_a();
antibfs(root);
for(int i=1; i<=m; ++i)
out << antibfs_res[i] << '\n';
return 0;
}