Pagini recente » Cod sursa (job #2071034) | Cod sursa (job #3136289) | Monitorul de evaluare | Cod sursa (job #856892) | Cod sursa (job #2869892)
#include <bits/stdc++.h>
using namespace std;
ifstream f("ahocorasick.in");
ofstream g("ahocorasick.out");
// #define f cin
// #define g cout
int af[102];
struct aho
{
aho *v[26], *exit, *par;
int cnt;
vector<int> leafs;
char ch;
aho()
{
for (int i = 0; i < 26; i++)
v[i] = nullptr;
exit = nullptr;
par = nullptr;
ch = cnt = 0;
leafs.clear();
}
} *rad = new aho();
struct box
{
aho *x;
box(aho *z)
{
x = z;
}
};
vector<box> vec;
void adauga(const string &, const int);
string s;
void getexit();
int32_t main()
{
f >> s;
int n;
f >> n;
for (int i = 1; i <= n; i++)
{
static string ax;
f >> ax;
adauga(ax, i);
}
getexit();
aho *ax = rad;
for (const char &ch : s)
{
if (ax->v[ch - 'a'] != nullptr)
ax = ax->v[ch - 'a'];
else
{
while (ax != rad)
{
ax = ax->exit;
if (ax->v[ch - 'a'] != nullptr)
break;
}
if (ax->v[ch - 'a'] != nullptr)
ax = ax->v[ch - 'a'];
}
if (ax != rad)
ax->cnt++;
}
reverse(vec.begin(), vec.end());
for (const auto &i : vec)
{
aho *ac = i.x;
for (const int &j : ac->leafs)
af[j] = ac->cnt;
ac->exit->cnt += ac->cnt;
}
for (int i = 1; i <= n; i++)
g << af[i] << '\n';
// g << endl;
// queue<box> q;
// q.push(box(rad));
// while (!q.empty())
// {
// aho *ac = q.front().x;
// for (int i = 0; i < 26; i++)
// if (ac->v[i] != nullptr)
// {
// q.push(box(ac->v[i]));
// g << ac->v[i]->ss << " " << ac->v[i]->par->ss << " " << ac->v[i]->exit->ss << " " << ac->v[i]->cnt << '\n';
// }
// q.pop();
// }
return 0;
}
void adauga(const string &s, const int ind)
{
aho *ax = rad;
for (const char &ch : s)
{
if (ax->v[ch - 'a'] == nullptr)
ax->v[ch - 'a'] = new aho;
ax->v[ch - 'a']->par = ax;
ax = ax->v[ch - 'a'];
ax->ch = ch - 'a';
}
ax->leafs.push_back(ind);
}
void getexit()
{
queue<box> q;
q.push(box(rad));
while (!q.empty())
{
aho *ac = q.front().x;
vec.push_back(q.front());
q.pop();
if (ac == rad || ac->par == rad)
ac->exit = rad;
else
{
aho *j = ac->par->exit;
while (j != rad && j->v[ac->ch] == nullptr)
j = j->par->exit;
if (j->v[ac->ch] != nullptr)
j = j->v[ac->ch];
ac->exit = j;
}
for (int i = 0; i < 26; i++)
if (ac->v[i] != nullptr)
q.push(box(ac->v[i]));
}
}