Pagini recente » Cod sursa (job #1506027) | Cod sursa (job #77004) | Cod sursa (job #2802719) | Cod sursa (job #3221730) | Cod sursa (job #2729728)
#include <bits/stdc++.h>
using namespace std;
ifstream in("ahocorasick.in");
ofstream out("ahocorasick.out");
const int sigma = 26;
const int max_c = (int)1e4 + 5;
const int max_n = (int)1e6 + 5;
struct Trie {
Trie *child[sigma];
Trie *fail;
vector<int> words;
int cnt;
Trie () {
fail = nullptr;
for (int i = 0; i < sigma; ++i) {
child[i] = nullptr;
}
cnt = 0;
}
};
int n, m;
char s[max_n];
char c[max_c];
Trie *root = new Trie();
int sol[max_c];
void insert(Trie *root, char *s, int id) {
Trie *p = root;
while (s[0] != '\0') {
if (p -> child[s[0] - 'a'] == nullptr) {
p -> child[s[0] - 'a'] = new Trie();
}
p = p -> child[s[0] - 'a'];
s++;
}
p -> words.push_back(id);
}
void aho() {
queue<Trie *> q;
root -> fail = nullptr;
for (int i = 0; i < sigma; ++i) {
if (root -> child[i] != nullptr) {
root -> child[i] -> fail = root;
q.push(root -> child[i]);
}
}
while ((int)q.size() > 0) {
Trie *parrent = q.front();
q.pop();
for (int i = 0; i < sigma; ++i) {
if (parrent -> child[i] != nullptr) {
q.push(parrent -> child[i]);
Trie *aux = parrent -> fail;
while (aux != root && aux -> child[i] == nullptr) {
aux = aux -> fail;
}
if (aux -> child[i] != nullptr) {
parrent -> child[i] -> fail = aux -> child[i];
} else {
parrent -> child[i] -> fail = root;
}
}
}
}
}
void solve(char *s) {
Trie *u = root;
while (s[0] != '\0') {
while (u != root && u -> child[s[0] - 'a'] == nullptr) {
u = u -> fail;
}
if (u -> child[s[0] - 'a'] != nullptr) {
u = u -> child[s[0] - 'a'];
}
u -> cnt++;
s++;
}
queue<Trie *> q;
q.push(root);
vector<Trie *> antibfs;
while ((int)q.size() > 0) {
Trie *parrent = q.front();
q.pop();
antibfs.push_back(parrent);
for (int i = 0; i < sigma; ++i) {
if (parrent -> child[i] != nullptr) {
q.push(parrent -> child[i]);
}
}
}
reverse(antibfs.begin(), antibfs.end());
for (Trie *u : antibfs) {
for (int i : u -> words) {
sol[i] += u -> cnt;
}
if (u -> fail != nullptr) {
u -> fail -> cnt += u -> cnt;
}
}
}
int main() {
in >> (s + 1) >> n;
for (int i = 1; i <= n; ++i) {
in >> c;
insert(root, c, i);
}
aho();
solve(s + 1);
for (int i = 1; i <= n; ++i) {
out << sol[i] << "\n";
}
return 0;
}