Pagini recente » Cod sursa (job #2749755) | Cod sursa (job #1893554) | Cod sursa (job #2560768) | Cod sursa (job #1019558) | Cod sursa (job #2526409)
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
int n;
struct trie{
int NrCuv;
int NrFii;
int sol;
trie *sufix;
trie *Fiu[26];
vector<trie *> v;
trie(){
NrFii = 0;
sol = 0;
sufix = NULL;
for(int i = 0;i<26;i++)
Fiu[i] = NULL;
v.clear();
}
};
trie *rad = new trie, *w[102];
queue<trie *> coada;
trie *adauga(char *s, trie *nod){
if(*s == 0){
return nod;
}
int lit = *s-'a';
if(nod->Fiu[lit] == NULL){
nod->Fiu[lit] = new trie;
nod->NrFii++;
}
return adauga(s+1, nod->Fiu[lit]);
}
void dfs(trie *root){
for(int i = 0;i<root->v.size();i++){
trie *vecin = root->v[i];
dfs(vecin);
root->sol += vecin->sol;
}
}
char a[1000002], x[10002];
int i;
int main(){
fin>>a;
fin>>n;
for(i=1;i<=n;i++){
fin>>x;
w[i] = adauga(x, rad);
}
coada.push(rad);
while(!coada.empty()){
trie *p = coada.front();
coada.pop();
for(i=0;i<26;i++)
if(p->Fiu[i]){
trie *aux = p->sufix;
while(aux && aux->Fiu[i] == NULL)
aux = aux->sufix;
if(aux == 0)
p->Fiu[i]->sufix = rad;
else
p->Fiu[i]->sufix = aux->Fiu[i];
p->Fiu[i]->sufix->v.push_back(p->Fiu[i]);
coada.push(p->Fiu[i]);
}
}
trie *crt = rad;
for(i=0;a[i]!=0;i++){
int lit = a[i]-'a';
while(crt && crt->Fiu[lit] == NULL)
crt = crt->sufix;
if(crt != 0){
crt->Fiu[lit]->sol++;
crt = crt->Fiu[lit];
}
else
crt = rad;
}
dfs(rad);
for(i=1;i<=n;i++)
fout<<w[i]->sol<<"\n";
return 0;
}