Pagini recente » Cod sursa (job #620641) | Cod sursa (job #1226854) | Cod sursa (job #1115412) | Cod sursa (job #1120066) | Cod sursa (job #1218320)
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream f("ahocorasick.in");
ofstream g("ahocorasick.out");
struct trie {
int nr;
trie *fiu[26], *back;
vector<trie*> v;
trie () {
nr = 0;
back = NULL;
for (int i=0; i<26; ++i)
fiu[i] = NULL;
}
} *T = new trie;
trie *Rez[105];
queue<trie*> Q;
char A[1000005], s[10005];
int n;
trie *Update (trie *nod, char *s) {
if (*s == 0)
return nod;
if (nod->fiu[*s - 'a'] == NULL)
nod->fiu[*s - 'a'] = new trie;
return Update (nod->fiu[*s - 'a'], s+1);
}
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;
Rez[i] = Update (T, s);
}
Q.push (T);
while ( !Q.empty() ) {
trie *nod = Q.front ();
Q.pop ();
for (int i=0; i<26; ++i) {
if (nod->fiu[i] != NULL) {
trie *aux = nod->back;
while (aux && !aux->fiu[i])
aux = aux->back;
if (!aux)
nod->fiu[i]->back = T;
else
nod->fiu[i]->back = aux->fiu[i];
nod->fiu[i]->back->v.push_back (nod->fiu[i]);
Q.push (nod->fiu[i]);
}
}
}
char *p;
trie *aux;
for (p = A, aux = T; *p; ++p) {
while (aux && !aux->fiu[*p - 'a'])
aux = aux->back;
if (!aux)
aux = T;
else
aux = aux->fiu[*p - 'a'];
++aux->nr;
}
DFS (T);
for (int i=1; i<=n; ++i)
g << Rez[i]->nr << "\n";
return 0;
}