Pagini recente » Cod sursa (job #405750) | Cod sursa (job #2147130) | Cod sursa (job #2966970) | Cod sursa (job #278311) | Cod sursa (job #1963656)
#include <cstdio>
#include <queue>
#include <cstring>
#include <unordered_set>
using namespace std;
struct Nod
{
Nod *fail;
Nod *vecini[26];
unordered_set<int> indici;
Nod()
{
fail = NULL;
for(int i = 0; i < 26; i++)
{
vecini[i] = NULL;
}
}
};
Nod *root;
const int N = 105;
char sir[1000005];
int n;
char dictionar[N][10005];
int nrAparitii[N];
void addCuvant(char x[], int nr)
{
Nod *a = root;
int l = strlen(x);
for(int i = 0; i < l; i++)
{
char ch = x[i] - 'a';
if(a->vecini[ch] == NULL)
{
a->vecini[ch] = new Nod();
a = a->vecini[ch];
}
else
{
a = a->vecini[ch];
}
}
a->indici.insert(nr);
}
void citire()
{
scanf("%s\n", &sir);
scanf("%d", &n);
for(int i = 0; i < n; i++)
{
scanf("%s\n", &dictionar[i]);
}
}
void construireTrie()
{
for(int i = 0; i < n; i++)
{
addCuvant(dictionar[i], i);
}
}
void pregatireAhoCorasick()
{
queue<Nod*> Q;
int l = 26;
for(int i = 0; i < l; i++)
{
if(root->vecini[i] != NULL)
{
Q.push(root->vecini[i]);
root->vecini[i]->fail = root;
}
}
while(Q.empty() == false)
{
Nod *r = Q.front();
Q.pop();
for(int i = 0; i < 26; i++)
{
if(r->vecini[i] != NULL)
{
Nod *u = r->vecini[i];
Nod *v = r->fail;
Q.push(u);
while(v->vecini[i] == NULL && v != root)
{
v = v->fail;
}
if(v->vecini[i] == NULL)
{
u->fail = root;
}
else
{
u->fail = v->vecini[i];
}
for(auto y : u->fail->indici)
{
u->indici.insert(y);
}
}
}
}
}
void ahoCorasick()
{
int l = strlen(sir);
Nod *q = root;
for(int i = 0; i < l; i++)
{
char ch = sir[i] - 'a';
while(q->vecini[ch] == NULL && q != root)
{
q = q->fail;
}
q = q->vecini[ch];
for(auto x : q->indici)
{
nrAparitii[x]++;
}
}
}
void afisare()
{
for(int i = 0; i < n; i++)
{
printf("%d\n", nrAparitii[i]);
}
}
int main()
{
freopen("ahocorasick.in", "r", stdin);
freopen("ahocorasick.out", "w", stdout);
root = new Nod();
citire();
construireTrie();
pregatireAhoCorasick();
ahoCorasick();
afisare();
return 0;
}