Pagini recente » Cod sursa (job #665355) | Cod sursa (job #674957) | Cod sursa (job #1759719) | Cod sursa (job #2272900) | Cod sursa (job #2664847)
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
using namespace std;
struct trie {
trie *k[26];
trie *f;
int sol;
vector<int> who;
trie() {
sol = 0;
f = 0;
for (int i = 0; i < 26; i++) {
k[i] = 0;
}
}
};
trie *root = new trie;
const int N = 100 + 7;
int sol[N];
vector<trie*> ord;
void ins(string s, int i) {
trie *cur = root;
for (auto &c : s) {
int x = c - 'a';
if (!cur->k[x]) {
cur->k[x] = new trie;
}
cur = cur->k[x];
}
cur->who.push_back(i);
}
void fo() {
queue<trie*> q;
q.push(root);
while (!q.empty()) {
trie* cur = q.front();
ord.push_back(cur);
q.pop();
for (int x = 0; x < 26; x++) {
if (cur->k[x]) {
q.push(cur->k[x]);
}
}
}
for (auto &cur : ord) {
for (int x = 0; x < 26; x++) {
if (cur->k[x]) {
trie *now = cur->k[x];
if (cur == root) {
now->f = root;
} else {
now->f = cur->f;
while (now->f != root && !now->f->k[x]) {
now->f = now->f->f;
}
if (now->f->k[x]) {
now->f = now->f->k[x];
}
}
}
}
}
}
int main() {
freopen ("ahocorasick.in", "r", stdin);
freopen ("ahocorasick.out", "w", stdout);
string s;
int dw;
cin >> s >> dw;
for (int i = 1; i <= dw; i++) {
string t;
cin >> t;
ins(t, i);
}
root->f = root;
fo();
trie *cur = root;
for (auto &c : s) {
int x = c - 'a';
while (cur != root && !cur->k[x]) {
cur = cur->f;
}
if (cur->k[x]) {
cur = cur->k[x];
}
cur->sol++;
}
reverse(ord.begin(), ord.end());
for (auto &x : ord) {
x->f->sol += x->sol;
}
for (auto &x : ord) {
for (auto &i : x->who) {
sol[i] = x->sol;
}
}
for (int i = 1; i <= dw; i++) {
cout << sol[i] << "\n";
}
}