Pagini recente » Cod sursa (job #2723980) | Cod sursa (job #4261) | Cod sursa (job #1511277) | Cod sursa (job #880966) | Cod sursa (job #2591391)
#include <cstdio>
#include <vector>
#include <queue>
#define fiu f[*s-'a']
using namespace std;
FILE *fin = fopen("ahocorasick.in", "r");
FILE *fout = fopen("ahocorasick.out", "w");
int n, i;
char A[1000005], s[10005];
struct trie {
int sol;
trie *f[26];
trie *back;
vector <trie *> v;
trie () {
sol = 0;
for (int i = 0; i < 26; ++i)
f[i] = 0;
back = 0;
v.clear();
}
};
trie *root = new trie();
trie *w[105], *nod, *aux;
queue <trie *> c;
trie *adauga(trie *r, char *s) {
if (*s == 0)
return r;
if (r->fiu == NULL)
r->fiu = new trie;
return adauga(r->fiu, s + 1);
}
void dfs(trie *nod) {
for (int i = 0; i < nod->v.size(); ++i) {
trie *vecin = nod->v[i];
dfs(vecin);
nod->sol += vecin->sol;
}
}
int main() {
fscanf(fin, "%s", &A); fscanf(fin, "%d", &n);
for (i = 1; i <= n; ++i) {
fscanf(fin, "%s", &s);
w[i] = adauga(root, s);
}
c.push(root);
while (!c.empty()) {
nod = c.front();
c.pop();
for (i = 0; i < 26; ++i)
if (nod->f[i]) {
aux = nod->back;
while (aux && aux->f[i] == NULL)
aux = aux->back;
if (aux == 0)
nod->f[i]->back = root;
else
nod->f[i]->back = aux->f[i];
nod->f[i]->back->v.push_back(nod->f[i]);
c.push(nod->f[i]);
}
}
aux = root;
for (i = 0; A[i] != 0; ++i) {
while (aux != root && aux->f[A[i] - 'a'] == NULL)
aux = aux->back;
if (aux->f[A[i] - 'a'] != NULL)
aux = aux->f[A[i] - 'a'];
aux->sol++;
}
dfs(root);
for (i = 1; i <= n; ++i)
fprintf(fout, "%d\n", w[i]->sol);
return 0;
}