Pagini recente » Cod sursa (job #418788) | Cod sursa (job #1729444) | Cod sursa (job #1004568) | Cod sursa (job #9626) | Cod sursa (job #2961570)
#include <fstream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;
ifstream in ("ahocorasick.in");
ofstream out ("ahocorasick.out");
const int sigma = 26, max_size = 1e2 + 1;
struct str{
int ct;
str * fii[sigma], * fail;
vector <int> cuv;
str()
{
ct = 0;
for (int i = 0; i < sigma; i++)
{
fii[i] = 0;
}
fail = 0;
}
};
str * t = new str;
int ans[max_size], sz;
vector <str *> v;
string s, cuvinte[max_size];
void ins (str * nod, int poz, int index)
{
if (poz == sz)
{
nod -> cuv.push_back(index);
return;
}
int urm = cuvinte[index][poz] - 'a';
if (nod -> fii[urm] == 0)
{
nod -> fii[urm] = new str;
}
ins(nod -> fii[urm], poz + 1, index);
}
void bfs ()
{
queue <str *> q;
q.push(t);
while (!q.empty())
{
str * nod = q.front();
q.pop();
v.push_back(nod);
for (int i = 0; i < sigma; i++)
{
if (nod -> fii[i] == 0)
continue;
str * fail = nod -> fail, * urm = nod -> fii[i];
q.push(urm);
if (nod == t)
{
urm -> fail = nod;
continue;
}
while (fail != t && fail -> fii[i] == 0)
{
fail = fail -> fail;
}
if (fail -> fii[i] != 0)
{
urm -> fail = fail -> fii[i];
}
else
{
urm -> fail = t;
}
}
}
}
void antibfs ()
{
reverse(v.begin(), v.end());
for (vector <str *> :: iterator it = v.begin(); it != v.end(); it++)
{
str * nod = * it;
if (nod == t)
continue;
nod -> fail -> ct += nod -> ct;
for (auto f : nod -> cuv)
{
ans[f] = nod -> ct;
}
}
}
int main ()
{
in >> s;
int n;
in >> n;
for (int i = 0; i < n; i++)
{
in >> cuvinte[i];
sz = cuvinte[i].size();
ins(t, 0, i);
}
bfs();
sz = s.size();
str * nod = t;
for (int i = 0; i < sz; i++)
{
int urm = s[i] - 'a';
while (nod != t && nod -> fii[urm] == 0)
{
nod = nod -> fail;
}
if (nod -> fii[urm] != 0)
{
nod = nod -> fii[urm];
}
nod -> ct++;
}
antibfs();
for (int i = 0; i < n; i++)
{
out << ans[i] << '\n';
}
in.close();
out.close();
return 0;
}