Pagini recente » Cod sursa (job #1996428) | Cod sursa (job #2121244) | Cod sursa (job #2935262) | Cod sursa (job #722508) | Cod sursa (job #2806707)
#include <fstream>
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;
ifstream f("ahocorasick.in");
ofstream g("ahocorasick.out");
struct nod
{
int parinte;
int last;
int sufix;
int aparitii;
int completari;
int copii[27];
};
vector <nod> trie;
char sir[1000005], cuvinte[105][10005];
int nr, poz_cuv[105];
void init(int index, int p)
{
nr++;
trie.push_back(nod());
trie[index].parinte = p;
trie[index].last = 26;
trie[index].aparitii = 0;
trie[index].completari = 0;
trie[index].sufix = -1;
for(int i=0; i<26; i++)
trie[index].copii[i] = 0;
}
void make_trie(char cuv[10005], int index)
{
if(nr==0)
{
init(0,0);
}
int len = strlen(cuv);
int poz = 0;
int litera;
for(int i=0; i<len; i++)
{
litera = cuv[i] - 'a';
if(trie[poz].copii[litera] == 0)
{
trie[poz].copii[litera] = nr;
init(nr,poz);
}
poz = trie[poz].copii[litera];
trie[poz].last = litera;
}
poz_cuv[index] = poz;
}
void make_sufix(int poz)
{
if(trie[poz].sufix == -1)
{
int litera = trie[poz].last;
int p = trie[poz].parinte;
if(p == 0)
{
trie[poz].sufix = 0;
}
else
{
do
{
if(trie[p].sufix == -1)
make_sufix(p);
p = trie[p].sufix;
}
while(trie[p].copii[litera] == 0 && p != 0);
trie[poz].sufix = trie[p].copii[litera];
//daca nici in radacina nu este ultima litera atunci sufixul este chiar radacina
}
}
}
void nr_aparitii()
{
int len = strlen(sir);
int poz = 0;
for (int i=0; i<len; i++)
{
int lit = sir[i] - 'a';
while(poz != -1 && trie[poz].copii[lit] == 0)
{
poz = trie[poz].sufix;
}
if(poz != -1)
{
poz = trie[poz].copii[lit];
trie[poz].aparitii++;
}
else
{
poz = 0;
}
}
}
void aparitii_din_sufixe()
{
int i;
for(i=1;i<nr;i++)
{
int poz = trie[i].sufix;
while(poz != 0)
{
trie[poz].completari += trie[i].aparitii;
poz = trie[poz].sufix;
}
}
}
int main()
{
int i,n;
f>>sir;
f>>n;
for(i=1; i<=n; i++)
{
f>>cuvinte[i];
make_trie(cuvinte[i],i);
}
for(i=1; i<=n; i++)
{
make_sufix(poz_cuv[i]);
}
nr_aparitii();
aparitii_din_sufixe();
for(i=1; i<=n; i++)
{
g<<trie[poz_cuv[i]].aparitii + trie[poz_cuv[i]].completari<<'\n';
}
return 0;
}