Pagini recente » Cod sursa (job #3133453) | Cod sursa (job #629143) | Cod sursa (job #707292) | Borderou de evaluare (job #2021504) | Cod sursa (job #1221088)
#include <fstream>
#include <iostream>
#include <vector>
#define fiu f[*s-'a']
#include <queue>
using namespace std;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
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();
char A[1000100], s[10010];
trie *w[101], *nod, *aux;
queue<trie *> Q;
int n;
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++) {
dfs(nod->v[i]);
nod->sol += nod->v[i]->sol;
}
// cout<<nod->sol<<" ";
}
int main(){
fin>>A;
fin>>n;
for (int i=1;i<=n;i++) {
fin>>s;
w[i] = adauga(root, s);
}
// construim la fiecare nod back
Q.push(root);
while (!Q.empty()) {
nod = Q.front();
Q.pop();
for (int i=0;i<26;i++) {
if (nod->f[i]) {
// construim back pentru 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]);
Q.push(nod->f[i]);
}
}
}
aux = root; // aux va reprezenta nodul din trie corespunzator caracterului la care sunt in A
for (int 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 (int i=1;i<=n;i++)
fout<<w[i]->sol<<"\n";
return 0;
}