Pagini recente » Borderou de evaluare (job #2322716) | Cod sursa (job #1062404) | Borderou de evaluare (job #2266674) | Cod sursa (job #1007723) | Cod sursa (job #1967282)
#include <cstdio>
#include <queue>
#include <cctype>
#include <cstring>
using namespace std;
struct Nod
{
int nr;
Nod *urm[26], *fail;
vector <int> cv;
Nod()
{
nr = 0;
for(int i = 0; i < 26; ++i)
urm[i] = 0;
fail = 0;
}
} *t, *q[10005*10005];
char s[1000002], aux[10002];
int nr,nrq, ans[102];
void inserare(char *p, Nod *n, int nr)
{
if(not isalpha(*p))
{
n->cv.push_back(nr);
return;
}
int lit = *p - 'a';
if(n->urm[lit] == 0)
n->urm[lit] = new Nod;
inserare(p+1,n->urm[lit],nr);
}
void citire()
{
scanf("%s", s);
scanf("%d", &nr);
for(int i = 1; i <= nr; ++i)
{
scanf("%s", aux);
///printf("%s\n", aux);
inserare(aux,t,i);
}
}
void bfs()
{
t->fail = t;
q[nrq++] = t;
for(int i = 0; i < nrq; ++i)
{
Nod *nod = q[i];
for(int lit = 0; lit < 26; ++lit)
if(nod->urm[lit])
{
Nod *fl = nod->fail;
while(fl != t && fl->urm[lit] == 0)
fl = fl->fail;
if(fl->urm[lit] && fl->urm[lit] != nod->urm[lit])
fl = fl->urm[lit];
nod->urm[lit]->fail = fl;
q[nrq++] = nod->urm[lit];
}
}
}
void potrivire()
{
int ln = strlen(s);
Nod *ps = t;
for(int i = 0; i < ln; ++i)
{
int lit = (int)s[i] - 'a';
while(ps != t && ps->urm[lit] == 0)
ps = ps->fail;
if(ps->urm[lit])
ps = ps->urm[lit];
ps->nr ++;
}
}
void suma()
{
for(int i = nrq - 1; i >= 0; --i)
{
q[i]->fail->nr += q[i]->nr;
for(vector<int>::iterator it = q[i]->cv.begin(); it != q[i]->cv.end(); ++it)
ans[*it] += q[i]->nr;
}
}
void afish()
{
for(int i = 1; i <= nr; ++i)
printf("%d\n", ans[i]);
}
int main()
{
freopen("ahocorasick.in", "r", stdin);
freopen("ahocorasick.out", "w", stdout);
t = new Nod;
citire();
bfs();
potrivire();
suma();
afish();
return 0;
}