Pagini recente » Cod sursa (job #3287554) | Cod sursa (job #2439695) | Cod sursa (job #1894811) | Cod sursa (job #1837427) | Cod sursa (job #2285906)
#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;
trieNode() {
for (int c = 0; c < 26; ++c) {
nxt[c] = nullptr;
}
}
} 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* node, trieNode* root) {
if (node->blue->wordIndex.size() != 0) {
node->green = node->blue;
}
else {
node->green = node->blue->green;
}
// pv(word);pn; /////
// pv(node);pv(node->myCnt);pn; //
// pv(node->blue);pv(node->green);pn; //
// pn; /////
for (int c = 'a'; c <= 'z'; ++c) {
if (node->nxt[c - 'a'] == nullptr) {
continue;
}
trieNode* urm = node->nxt[c - 'a'];
trieNode* curr = node->blue;
while (curr != root && curr->nxt[c - 'a'] == nullptr) {
curr = curr->blue;
}
if (curr->nxt[c - 'a'] == nullptr || curr->nxt[c - 'a'] == urm) {
urm->blue = root;
}
else {
urm->blue = curr->nxt[c - 'a'];
}
build(urm, root);
}
}
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, &root);
vector<int> occ = solve(&root, text, N);
for (int o : occ) {
out << o << '\n';
}
return 0;
}