Pagini recente » Cod sursa (job #46447) | Cod sursa (job #2205189) | Cod sursa (job #1921365) | Cod sursa (job #533627) | Cod sursa (job #2285934)
#include <bits/stdc++.h>
using namespace std;
#if 1
#define pv(x) cerr<<#x<<" = "<<(x)<<"; ";cerr.flush()
#define pn cerr<<endl
#else
#define pv(x)
#define pn
#endif
// #if 1
#ifdef INFOARENA
ifstream in("ahocorasick.in");
ofstream out("ahocorasick.out");
#else
#define in cin
#define out cout
#endif
using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pld = pair<ld, ld>;
using pdd = pair<double, double>;
#define pb push_back
const long double PI = 3.14159265358979323846264338327950288419716939937510582097494459230781640628620899862;
const long double EPS = 1e-8;
const int inf_int = 1e9 + 5;
const ll inf_ll = 1e18 + 5;
const int NMax = 2e5 + 5;
const int mod = 666013;
const int dx[] = {-1,0,0,+1}, dy[] = {0,-1,+1,0};
struct trieNode {
trieNode* nxt[26] = {};
trieNode* blue = this, *green = this;
vector<int> wordIndex;
} root;
void add(trieNode* node, const string& word, uint idx, int widx) {
if (idx == word.size()) {
node->wordIndex.pb(widx);
return;
}
int let = word[idx] - 'a';
if (node->nxt[let] == nullptr) {
node->nxt[let] = new trieNode;
}
add(node->nxt[let], word, idx + 1, widx);
}
void build(trieNode* root) {
queue<trieNode*> Q;
for (char c = 'a'; c <= 'z'; ++c) {
int let = c - 'a';
if (root->nxt[let] == nullptr) {
root->nxt[let] = root;
}
else {
trieNode* urm = root->nxt[let];
urm->blue = urm->green = root;
Q.push(urm);
}
}
while (Q.size()) {
trieNode* node = Q.front();
Q.pop();
for (char c = 'a'; c <= 'z'; ++c) {
int let = c - 'a';
if (node->nxt[let] == nullptr) {
continue;
}
trieNode* urm = node->nxt[let];
trieNode* curr = node->blue;
while (curr->nxt[let] == nullptr) {
curr = curr->blue;
}
urm->blue = (curr->nxt[let] != urm) ? curr->nxt[let] : root;
if (urm->blue->wordIndex.size() != 0) {
urm->green = urm->blue;
}
else {
urm->green = urm->blue->green;
}
Q.push(urm);
}
}
}
vector<int> solve(trieNode* root, const string& text, const int dictSize) {
vector<int> occ(dictSize);
trieNode* node = root;
for (uint tidx = 0; tidx < text.size(); ++tidx) {
int let = text[tidx] - 'a';
while (node != root && node->nxt[let] == nullptr) {
node = node->blue;
}
node = (node->nxt[let] == nullptr) ? root : node->nxt[let];
trieNode* curr = node;
while (curr != root) {
for (int idx : curr->wordIndex) {
occ[idx] += 1;
}
curr = curr->green;
}
}
return occ;
}
int main() {
cin.sync_with_stdio(false);
cin.tie(0);cout.tie(0);
string text;
in >> text;
int N;
in >> N;
for (int i = 0; i < N; ++i) {
string word;
in >> word;
add(&root, word, 0, i);
}
build(&root);
vector<int> occ = solve(&root, text, N);
for (int o : occ) {
out << o << '\n';
}
return 0;
}