Pagini recente » Cod sursa (job #686731) | Cod sursa (job #2290566) | Cod sursa (job #571740) | Cod sursa (job #2889157) | Cod sursa (job #2593014)
#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct Trie {
vector<int> id;
Trie *kids[26];
Trie *fail;
int sol;
Trie() {
id.clear();
for (int i = 0; i < 26; i++) {
kids[i] = 0;
}
fail = 0;
sol = 0;
}
};
Trie *root = new Trie;
void ins(string s, int i) {
Trie *now = root;
for (auto &c : s) {
int x = c - 'a';
if (!now->kids[x]) {
now->kids[x] = new Trie;
}
now = now->kids[x];
}
now->id.push_back(i);
}
vector<Trie*> ord;
void build() {
root->fail = root;
queue<Trie*> q;
for (int k = 0; k < 26; k++) {
if (root->kids[k]) {
root->kids[k]->fail = root;
q.push(root->kids[k]);
}
}
ord.push_back(root);
while (!q.empty()) {
auto now = q.front();
ord.push_back(now);
q.pop();
for (int k = 0; k < 26; k++) {
if (now->kids[k]) {
Trie *val = now->fail;
while (val != root && !val->kids[k]) {
val = val->fail;
}
if (val->kids[k]) {
val = val->kids[k];
}
now->kids[k]->fail = val;
q.push(now->kids[k]);
}
}
}
}
int sol[107];
int main() {
freopen ("ahocorasick.in", "r", stdin);
freopen ("ahocorasick.out", "w", stdout);
string s;
cin >> s;
int m;
cin >> m;
for (int i = 1; i <= m; i++) {
string t;
cin >> t;
ins(t, i);
}
build();
Trie *now = root;
for (auto &c : s) {
int x = c - 'a';
while (now != root && !now->kids[x]) {
now = now->fail;
}
if (now->kids[x]) {
now = now->kids[x];
}
now->sol++;
}
reverse(ord.begin(), ord.end());
for (auto &now : ord) {
for (auto &i : now->id) {
sol[i] += now->sol;
}
now->fail->sol += now->sol;
}
for (int i = 1; i <= m; i++) {
cout << sol[i] << "\n";
}
}