Pagini recente » Cod sursa (job #1784993) | Cod sursa (job #1047025) | Cod sursa (job #3128386) | Cod sursa (job #1694054) | Cod sursa (job #2641837)
#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct Trie {
Trie *kids[26];
Trie *fail;
int f;
vector<int> v;
string s;
Trie() {
for (int j = 0; j < 26; j++) {
kids[j] = 0;
}
s = "";
fail = 0;
f = 0;
v.clear();
}
};
Trie *root = new Trie;
int n;
string s;
string t;
vector<Trie*> ord;
void build_fail() {
for (auto &now : ord) {
for (int x = 0; x < 26; x++) {
if (now->kids[x]) {
Trie *cur = now->fail;
while (cur != root && !cur->kids[x]) {
cur = cur->fail;
}
if (now != root && cur->kids[x]) {
cur = cur->kids[x];
}
now->kids[x]->fail = cur;
}
}
}
}
void calc_order() {
queue<Trie*> q;
q.push(root);
while (!q.empty()) {
Trie *now = q.front();
ord.push_back(now);
q.pop();
for (int x = 0; x < 26; x++) {
if (now->kids[x]) {
q.push(now->kids[x]);
}
}
}
}
int main() {
freopen ("ahocorasick.in", "r", stdin);
freopen ("ahocorasick.out", "w", stdout);
cin >> s >> n;
vector<int> ans(n);
for (int i = 1; i <= n; i++) {
cin >> t;
Trie *now = root;
for (auto &ch : t) {
int x = ch - 'a';
if (!now->kids[x]) {
now->kids[x] = new Trie;
now->kids[x]->s = now->s + ch;
}
now = now->kids[x];
}
now->v.push_back(i - 1);
}
root->fail = root;
calc_order();
build_fail();
Trie *now = root;
for (auto &ch : s) {
int x = ch - 'a';
while (now != root && !now->kids[x]) {
now = now->fail;
}
if (now->kids[x]) {
now = now->kids[x];
}
now->f++;
}
reverse(ord.begin(), ord.end());
for (auto &it : ord) {
it->fail->f += it->f;
for (auto &j : it->v) {
ans[j] += it->f;
}
}
for (auto &x : ans) {
cout << x << "\n";
}
return 0;
}