Pagini recente » Cod sursa (job #2587569) | Cod sursa (job #304836) | Cod sursa (job #2280755) | Cod sursa (job #163622) | Cod sursa (job #2193464)
#include <bits/stdc++.h>
using namespace std;
vector <int> lvls[100010];
vector <vector <int>> v;
vector <int> fail, letter, frc;
int words[100010];
int nou(int q)
{
int x = v.size();
v.push_back(vector <int> (27));
fail.push_back(0);
letter.push_back(q);
frc.push_back(0);
return x;
}
void add(string s, int word)
{
int root = 0;
int lvl(0);
for (auto & i : s) {
i -= 'a';
lvl++;
if (!v[root][i]) {
int x = nou(i);
v[root][i] = x;
lvls[lvl].push_back(x);
}
root = v[root][i];
}
words[word] = root;
}
void calc_fail()
{
for (int x(0); x <= 100000; x++) {
for (auto i : lvls[x]) {
while (fail[i] &&
(!v[fail[i]][letter[i]] || v[fail[i]][letter[i]] == i))
fail[i] = fail[fail[i]];
if (v[fail[i]][letter[i]] &&
v[fail[i]][letter[i]] != i)
fail[i] = v[fail[i]][letter[i]];
for (int j(0); j < 26; j++)
if (v[i][j])
fail[v[i][j]] = fail[i];
}
}
}
void calc_ans()
{
for (int x(100000); x >= 0; x--)
for (auto i : lvls[x])
frc[fail[i]] += frc[i];
}
int main()
{
ifstream in("ahocorasick.in");
ofstream out("ahocorasick.out");
string s;
in >> s;
nou(-1);
int n;
in >> n;
for (int i(1); i <= n; i++) {
string q;
in >> q;
add(q, i);
}
calc_fail();
int root = 0;
for (auto i : s) {
while (root && !v[root][i - 'a'])
root = fail[root];
if (v[root][i - 'a'])
root = v[root][i - 'a'];
frc[root]++;
}
calc_ans();
for (int i(1); i <= n; i++)
out << frc[words[i]] << '\n';
return 0;
}