Pagini recente » Cod sursa (job #2733304) | Cod sursa (job #3350744) | Cod sursa (job #1040571) | Cod sursa (job #773859) | Cod sursa (job #3323387)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
typedef long long ll;
typedef long double ld;
const int N = 1e2 + 5;
const int alpha = 26;
int n;
string s, t;
struct nod
{
int cnt;
nod *suflink, *v[alpha];
nod()
{
cnt = 0;
suflink = NULL;
for (int i = 0; i < alpha; i++)
v[i] = NULL;
}
} *root, *termnodes[N];
bool haschild(nod *x, int a)
{
return (x->v[a] == NULL) ? false : true;
}
nod* inserare() // string t
{
nod *x = root;
for (char c : t)
{
int a = c - 'a';
if (!haschild(x, a))
x->v[a] = new nod;
x = x->v[a];
}
return x;
}
void solveprefix(nod *x, int a)
{
nod *pref = x->suflink;
while (pref != root && !haschild(pref, a))
pref = pref->suflink;
if (haschild(pref, a) && pref != x)
x->v[a]->suflink = pref->v[a];
else
x->v[a]->suflink = root;
}
void build()
{
root->suflink = root;
queue<nod*> q;
q.push(root);
while (!q.empty())
{
nod *x = q.front();
q.pop();
for (int i = 0; i < alpha; i++)
if (haschild(x, i))
{
solveprefix(x, i);
q.push(x->v[i]);
}
}
}
void solve()
{
nod *x = root;
for (char c : s)
{
int a = c - 'a';
while (x != root && !haschild(x, a))
x = x->suflink;
if (haschild(x, a))
x = x->v[a];
x->cnt++;
}
vector<nod*> bfsOrder;
bfsOrder.push_back(root);
for (int i = 0; i < bfsOrder.size(); i++)
{
nod* node = bfsOrder[i];
for (int j = 0; j < alpha; j++)
if (haschild(node, j))
bfsOrder.push_back(node->v[j]);
}
for (int i = bfsOrder.size() - 1; i >= 0; i--)
{
bfsOrder[i]->suflink->cnt += bfsOrder[i]->cnt;
}
}
int main()
{
fin >> s >> n;
root = new nod;
for (int i = 1; i <= n; i++)
{
fin >> t;
termnodes[i] = inserare();
}
build();
solve();
for (int i = 1; i <= n; i++)
fout << termnodes[i]->cnt << '\n';
return 0;
}