Pagini recente » Cod sursa (job #996692) | Cod sursa (job #2877656) | Cod sursa (job #1583792) | Istoria paginii runda/k | Cod sursa (job #2869880)
#include <bits/stdc++.h>
using namespace std;
ifstream f("ahocorasick.in");
ofstream g("ahocorasick.out");
// #define f cin
// #define g cout
int rez[102], af[102];
struct aho
{
aho *v[26], *exit, *par;
int cnt, def;
vector<int> leafs;
char ch;
string ss;
aho()
{
for (int i = 0; i < 26; i++)
v[i] = nullptr;
exit = nullptr;
par = nullptr;
def = 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();
// void dfs(box);
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'];
}
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;
}
// ax = rad;
// dfs(box(ax));
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 dfs(box ax)
// {
// aho *ac = ax.x;
// for (int i = 0; i < 26; i++)
// if (ac->v[i] != nullptr)
// {
// dfs(box(ac->v[i]));
// // ac->cnt += ac->v[i]->cnt;
// }
// ac->exit->cnt += ac->cnt;
// cout << ac->ss << " " << ac->cnt << '\n';
// // ac->cnt += ac->def;
// for (const auto i : ac->leafs)
// af[i] += ac->cnt;
// }
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->ss = ax->par->ss + ch;
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]));
}
}