Pagini recente » Cod sursa (job #579707) | Cod sursa (job #3194762) | Cod sursa (job #768284) | Cod sursa (job #1366722) | Cod sursa (job #721717)
Cod sursa(job #721717)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N ('z' - 'a' + 1)
typedef struct trie_node {
int counter;
struct trie_node *children[N];
} trie;
trie *new_node() {
trie *t;
t = (trie *)malloc(sizeof(trie));
t->counter = 0;
memset(t->children, 0, sizeof(t->children));
return t;
}
void insert(trie *t, char *str) {
if (*str == '\0')
return;
int index = str[0] - 'a';
if (!t->children[index])
t->children[index] = new_node();
t->children[index]->counter++;
insert(t->children[index], str + 1);
}
int counter(trie *t, char *word) {
if (*word == '\0')
return t->counter;
int index = word[0] - 'a';
return counter(t->children[index], word + 1);
}
void print(trie *t) {
printf("%d\n", t->counter);
int i;
for (i=0;i<N;i++) {
if (t->children[i]) {
printf("%c\n", i + 'a');
print(t->children[i]);
}
}
}
static char line[1000002];
static char word[10002];
int main() {
freopen("ahocorasick.in", "r", stdin);
freopen("ahocorasick.out", "w", stdout);
trie *t = new_node();
fgets(line, 1000001, stdin);
int nl = strlen(line), i;
line[nl - 1] = '\0';
nl--;
for (i=0;i<nl;i++) {
insert(t, line + i);
}
int n, k;
scanf("%d", &n);
for (k=0;k<n;) {
word[0] = '\0';
fgets(word, 10001, stdin);
int nw = strlen(word);
if (word[nw - 1] == '\n') {
word[nw - 1] = '\0';
nw--;
}
if (!nw) continue;
k++;
word[nw] = '\0';
printf("%d\n", counter(t, word));
}
return 0;
}