Pagini recente » Cod sursa (job #2754624) | Cod sursa (job #846642) | Cod sursa (job #2400437) | Cod sursa (job #2066643) | Cod sursa (job #1232258)
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
ifstream ka("ahocorasick.in");
ofstream ki("ahocorasick.out");
const int N_MAX = 100;
int aparitii[N_MAX + 1];
struct nod
{
bool bun; // final de cuvant
int nr; // indicele cuvantului
nod* fii[26];
nod* suffix; // fail node
nod* blue; // output link
nod()
{
bun = false;
nr = 0;
for(int i = 0; i < 26; i++)
fii[i] = NULL;
suffix = NULL;
blue = NULL;
}
};
queue <nod*> coada;
string s, cuv;
int tot, k;
void adaugare(nod* n, int poz)
{
if(poz == cuv.size())
{
n->bun = true;
n->nr = ++k;
}
else if(n->fii[cuv[poz] - 'a'] == NULL)
{
nod* nn = new(nod);
n->fii[cuv[poz] - 'a'] = nn;
adaugare(nn, poz + 1);
}
else
{
adaugare(n->fii[cuv[poz] - 'a'], poz + 1);
}
}
int main()
{
ka >> s >> tot;
nod* radacina = new(nod);
for(int i = 1; i <= tot; i++)
{
ka >> cuv;
adaugare(radacina, 0);
}
for(int i = 0; i < 26; i++)
{
if(radacina->fii[i] != NULL)
{
radacina->fii[i]->suffix = radacina;
coada.push(radacina->fii[i]);
}
}
while(!coada.empty())
{
nod* r = coada.front();
coada.pop();
for(int i = 0; i < 26; i++)
{
if(r->fii[i] != NULL)
{
nod* n = r->suffix;
while(n != NULL && n->fii[i] == NULL)
{
n = n->suffix;
}
if(n == NULL)
r->fii[i]->suffix = radacina;
else
{
r->fii[i]->suffix = n->fii[i];
if(n->fii[i]->bun)
r->fii[i]->blue = n->fii[i];
else
r->fii[i]->blue = n->fii[i]->blue;
}
coada.push(r->fii[i]);
}
}
}
nod* n = radacina;
for(int i = 0; i < s.size(); i++)
{
while(n != NULL && n->fii[s[i] - 'a'] == NULL)
n = n->suffix;
if(n == NULL)
n = radacina;
else
n = n->fii[s[i] - 'a'];
nod* f = n;
if(f->bun)
aparitii[f->nr]++;
while(f->blue != NULL)
{
f = f->blue;
aparitii[f->nr]++;
}
}
for(int i = 1; i <= tot; i++)
ki << aparitii[i] << '\n';
return 0;
}