Pagini recente » Cod sursa (job #669321) | Cod sursa (job #772093) | Cod sursa (job #1507405) | Cod sursa (job #1446335) | Cod sursa (job #2668421)
#include <cstdio>
#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[1000003];
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];
}
}
}
void match_a(int n) {
ahocor * current_node = root;
int current_son = 0;
for(int i=0; i<n; ++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() {
freopen("ahocorasick.in", "r", stdin);
freopen("ahocorasick.out", "w", stdout);
scanf("%s", a);
int n = strlen(a), m, current_n;
if(a[n-1] == '\n') {
--n;
a[n] = 0;
}
root = new ahocor;
scanf("%d", &m);
for(int i=1; i<=m; ++i) {
scanf("%s", current_word);
current_n = strlen(current_word);
if (current_word[current_n] == '\n') {
--current_n;
current_word[current_n] = 0;
}
insert_ahocor(root, current_word, i);
}
bfs(root);
match_a(n);
antibfs(root);
for(int i=1; i<=m; ++i)
printf("%d\n", antibfs_res[i]);
return 0;
}