Pagini recente » Cod sursa (job #1614345) | Cod sursa (job #1481446) | Cod sursa (job #903525) | Cod sursa (job #1991005) | Cod sursa (job #1683812)
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
const int MAXN = 1000005;
ifstream in("ahocorasick.in");
ofstream out("ahocorasick.out");
struct nod_corasick
{
static const int SIGMA = 'z' - 'a' + 1;
vector<int> siruri;//sirurile care se termina in nodul curent
int nr_potriviri;//numarul de potriviri din nodul curent sau din fii lui
nod_corasick *fii[SIGMA];
nod_corasick *intoarcere;
nod_corasick()
{
nr_potriviri = 0;
intoarcere = NULL;
memset(fii, 0, sizeof(fii));
}
void inserare(char *s, int id)
{
if (*s == 0)
{
siruri.push_back(id);
return;
}
int idc = *s - 'a';
if (fii[idc] == 0)
fii[idc] = new nod_corasick;
fii[idc] -> inserare(s + 1, id);
}
};
const int MAXCUVANT = 10005;
nod_corasick *coada[MAXCUVANT * MAXCUVANT];
int pcoada,qcoada;
struct corasick
{
static const int NRCUVINTE = 105;
static const int SIGMA = 'z' - 'a' + 1;
nod_corasick *radacina;
int nrcuv;
int raspuns[NRCUVINTE];
corasick()
{
radacina = new nod_corasick;
nrcuv = 0;
//memset(coada, 0, sizeof(coada));
pcoada = 1;
qcoada = 0;
memset(raspuns, 0, sizeof(raspuns));
}
void adaugare_cuvant(char *s)
{
++nrcuv;
radacina -> inserare(s, nrcuv);
}
void bfs()
{
nod_corasick *pred;//unde o sa indice intoarcere fiecarui nod
radacina -> intoarcere = radacina;
pcoada = 1;
qcoada = 1;
coada[1] = radacina;
while (pcoada <= qcoada)
{
nod_corasick *nod = coada[pcoada];
++pcoada;
for (int i = 0;i < SIGMA;++i)
if (nod -> fii[i] != NULL)
{
for (pred = nod -> intoarcere; pred != radacina && pred -> fii[i] == NULL; pred = pred -> intoarcere)
;
if (pred -> fii[i] != NULL && pred -> fii[i] != nod -> fii[i])
pred = pred -> fii[i];
nod -> fii[i] -> intoarcere = pred;
coada[++qcoada] = nod -> fii[i];
}
}
radacina -> intoarcere = NULL;
}
void antibfs()
{
for (int i = qcoada;i > 0;--i)
{
nod_corasick *nod = coada[i];
if(nod -> intoarcere != NULL)
nod -> intoarcere -> nr_potriviri += nod -> nr_potriviri;
for (unsigned int j = 0;j < nod -> siruri.size();++j)
raspuns[nod -> siruri[j]] = nod -> nr_potriviri;
}
}
void gestionare_sir(char *s)
{
nod_corasick *p = radacina;
for (int i = 0;s[i] != 0;++i)
{
int urm = s[i] - 'a';
//cautam o muchie pe care sa putem merge in jos
while(p -> fii[urm] == NULL && p != radacina)
p = p -> intoarcere;
if (p -> fii[urm] != NULL)
p = p -> fii[urm];
++(p -> nr_potriviri);
}
antibfs();
}
};
corasick *cora;
int main()
{
cora = new corasick;
char *sir = new char[MAXN];
int n;
char cuv[MAXCUVANT];
in >> sir;
in >> n;
for (int i = 1;i <= n;++i)
{
//memset(cuv, 0, sizeof(cuv));
in >> cuv;
cora -> adaugare_cuvant(cuv);
}
cora -> bfs();
cora -> gestionare_sir(sir);
for (int i = 1;i <= n;++i)
out << cora -> raspuns[i] << '\n';
return 0;
}