Pagini recente » Cod sursa (job #2941892) | Cod sursa (job #1141343) | Cod sursa (job #1841421) | Cod sursa (job #1873374) | Cod sursa (job #2591385)
#include <cstdio>
#include <vector>
#include <queue>
#define fiu f[*s - 'a']
using namespace std;
FILE *in = fopen("ahocorasick.in", "r");
FILE *out = fopen("ahocorasick.out", "w");
int n;
char A[1000001], s[10001];
struct trie {
int sol;
trie *f[26], *back;
vector <trie*> v;
trie() {
sol = 0, back = 0;
for (int i = 0; i < 26; ++i)
f[i] = 0;
v.clear();
}
};
trie *root = new trie(), *rez[101], *aux, *nod;
queue <trie*> q;
trie *inserare(trie *r, char *s) {
if (*s == 0)
return r;
if (r->fiu == NULL)
r->fiu = new trie;
return inserare(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(in, "%s", &A); fscanf(in, "%d", &n);
for (int i = 1; i <= n; ++i) {
fscanf(in, "%s", &s);
rez[i] = inserare(root, s);
}
q.push(root);
while (!q.empty()) {
nod = q.front();
q.pop();
for (int i = 0; i < 26; ++i) {
if (nod->f[i]) {
aux = nod->back;
while (aux && aux->f[i] == NULL)
aux = aux->back;
if (!aux)
nod->f[i]->back = root;
else
nod->f[i]->back = aux->f[i];
nod->f[i]->back->v.push_back(nod->f[i]);
q.push(nod->f[i]);
}
}
}
aux = root;
for (int i = 0; A[i]; ++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 (int i = 1; i <= n; ++i)
fprintf(out, "%d\n", rez[i]->sol);
return 0;
}