Pagini recente » Cod sursa (job #2374779) | Cod sursa (job #1609877) | Istoria paginii runda/123abc | Cod sursa (job #855154) | Cod sursa (job #1226749)
#include <fstream>
#include <vector>
#include <queue>
#define DIMM 1000001
#define DIM 10001
using namespace std;
ifstream f("ahocorasick.in");
ofstream g("ahocorasick.out");
struct trie {
int nr;
trie *back, *fii[26];
vector<trie*> v;
trie() {
back = NULL;
nr = 0;
for (int i = 0; i < 26; ++i)
fii[i] = NULL;
}
} *T = new trie;
trie *Res[101];
int n;
char A[DIMM], s[DIM];
trie *update(trie *nod, char *s) {
if (*s == 0)
return nod;
if (nod->fii[*s - 'a'] == NULL)
nod->fii[*s - 'a'] = new trie;
return update(nod->fii[*s - 'a'], s + 1);
}
void BFS() {
queue<trie*> Q;
Q.push(T);
while (!Q.empty()) {
trie *nod = Q.front();
Q.pop();
for (int i = 0; i < 26; ++i)
if (nod->fii[i] != NULL) {
trie *aux = nod->back;
while (aux && !aux->fii[i])
aux = aux->back;
if (!aux)
aux = T;
else
aux = aux->fii[i];
nod->fii[i]->back = aux;
aux->v.push_back(nod->fii[i]);
Q.push(nod->fii[i]);
}
}
}
void DFS(trie* nod) {
for (vector<trie*>::iterator it = nod->v.begin(); it != nod->v.end(); ++it) {
DFS(*it);
nod->nr += (*it)->nr;
}
}
int main() {
f >> A;
f >> n;
for (int i = 1; i <= n; ++i) {
f >> s;
Res[i] = update(T, s);
}
BFS();
trie *aux = T;
for (char *p = A; *p; ++p) {
while (aux && !aux->fii[*p - 'a'])
aux = aux->back;
if (!aux)
aux = T;
else
aux = aux->fii[*p - 'a'];
++aux->nr;
}
DFS(T);
for (int i = 1; i <= n; ++i)
g << Res[i]->nr << "\n";
return 0;
}