Pagini recente » Cod sursa (job #1042965) | Cod sursa (job #1264131) | Cod sursa (job #1982148) | Cod sursa (job #622985) | Cod sursa (job #3208799)
#include <fstream>
using namespace std;
ifstream cin ("ahocorasick.in");
ofstream cout ("ahocorasick.out");
struct Aho_Corasick {
Aho_Corasick *urmatorul[26] = { } , *anterior = NULL;
int termen = 0;
} *aparitii = new Aho_Corasick , *locatie[101] , *coada[1000001];
char sir[1000001];
Aho_Corasick* Insert (const char sir[])
{
Aho_Corasick *nod_actual = aparitii;
for (int indice = 0 ; sir[indice] ; nod_actual = nod_actual -> urmatorul[sir[indice++] - 'a']) {
if (!nod_actual -> urmatorul[sir[indice] - 'a'])
{ nod_actual -> urmatorul[sir[indice] - 'a'] = new Aho_Corasick; }
}
return nod_actual;
}
void Solve ()
{
int stanga = 1 , dreapta = 0;
aparitii -> anterior = aparitii;
for (coada[++dreapta] = aparitii ; stanga <= dreapta ; stanga++)
{
Aho_Corasick *nod_actual = coada[stanga];
for (int indice = 0 ; indice < 26 ; indice++) {
if (nod_actual -> urmatorul[indice])
{
Aho_Corasick *nod_vecin = nod_actual -> urmatorul[indice] , *candidat = nod_actual -> anterior;
while (candidat != aparitii && !candidat -> urmatorul[indice])
{ candidat = candidat -> anterior; }
if (candidat -> urmatorul[indice] && candidat -> urmatorul[indice] != nod_vecin)
{ candidat = candidat -> urmatorul[indice]; }
nod_vecin -> anterior = candidat;
coada[++dreapta] = nod_vecin;
}
}
}
{
Aho_Corasick *nod_actual = aparitii;
for (int indice = 0 ; sir[indice] ; indice++)
{
while (nod_actual != aparitii && !nod_actual -> urmatorul[sir[indice] - 'a'])
{ nod_actual = nod_actual -> anterior; }
if (nod_actual -> urmatorul[sir[indice] - 'a'])
{ nod_actual = nod_actual -> urmatorul[sir[indice] - 'a']; }
nod_actual -> termen++;
}
}
for (stanga = dreapta ; stanga > 1 ; stanga--)
{ coada[stanga] -> anterior -> termen += coada[stanga] -> termen; }
}
int main ()
{
int numar_cuvinte;
cin >> sir >> numar_cuvinte;
for (int indice = 1 ; indice <= numar_cuvinte ; indice++)
{ char cuvant[10001]; cin >> cuvant; locatie[indice] = Insert(cuvant); }
Solve();
for (int indice = 1 ; indice <= numar_cuvinte ; indice++)
{ cout << locatie[indice] -> termen << '\n'; }
cout.close(); cin.close();
return 0;
}