Pagini recente » Cod sursa (job #705074) | Cod sursa (job #492898) | Cod sursa (job #2007635) | Cod sursa (job #1782550) | Cod sursa (job #2286051)
#include <bits/stdc++.h>
#if 1
#define pv(x) std::cerr<<#x<<" = "<<(x)<<"; ";std::cerr.flush()
#define pn std::cerr<<std::endl
#else
#define pv(x)
#define pn
#endif
// #if 1
#ifdef INFOARENA
std::ifstream in("ahocorasick.in");
std::ofstream out("ahocorasick.out");
#else
#define in cin
#define out cout
#endif
class ahoCorasick {
private:
static const char minChar = 'a', maxChar = 'z';
static const int alphabetSize = maxChar - minChar + 1;
std::vector<std::string> dictionary;
int dictionarySize = 0;
struct trieNode {
int num = 0, length = 0;
std::vector<int> wordIndex;
trieNode* blue = this;
trieNode* nxt[alphabetSize] = {};
} *root;
std::vector<trieNode*> Q;
bool resetNeeded = false;
public:
ahoCorasick(std::vector<std::string> _dictionary, bool saveDict = false) {
if (saveDict) {
dictionary = _dictionary;
}
dictionarySize = _dictionary.size();
root = new trieNode;
for (int i = 0; i < (int)_dictionary.size(); ++i) {
add(root, _dictionary[i], 0, i);
}
built(root);
}
std::vector<std::string> getDictionary() {
return dictionary;
}
void getNumberOfOccurences(const std::string& text, std::vector<int>& occ) {
occ.assign(dictionarySize, 0);
if (resetNeeded) {
reset();
}
resetNeeded = true;
trieNode* node = root;
for (int tdx = 0; tdx < (int)text.size(); ++tdx) {
char c = text[tdx];
int let = c - minChar;
while (node->nxt[let] == nullptr) {
node = node->blue;
}
node = node->nxt[let];
node->num += 1;
}
for (int qdx = Q.size() - 1; qdx >= 0; --qdx) {
trieNode* node = Q[qdx];
for (int wdx : node->wordIndex) {
occ[wdx] += node->num;
}
node->blue->num += node->num;
}
}
private:
void add(trieNode* node, const std::string& word, int idx, int wdx) {
node->length = idx;
if (idx == (int)word.size()) {
node->wordIndex.push_back(wdx);
return;
}
int let = word[idx] - minChar;
if (node->nxt[let] == nullptr) {
node->nxt[let] = new trieNode;
}
add(node->nxt[let], word, idx + 1, wdx);
}
void built(trieNode* root) {
for (int let = 0; let < alphabetSize; ++let) {
if (root->nxt[let] == nullptr) {
root->nxt[let] = root;
}
else {
trieNode* follow = root->nxt[let];
follow->blue = root;
Q.push_back(follow);
}
}
int qdx = 0;
while (qdx < (int)Q.size()) {
trieNode *node = Q[qdx++];
for (char c = minChar; c <= maxChar; ++c) {
int let = c - minChar;
trieNode* follow = node->nxt[let];
if (follow == nullptr) {
continue;
}
trieNode* aux = node->blue;
while (aux->nxt[let] == nullptr) {
aux = aux->blue;
}
aux = aux->nxt[let];
follow->blue = (aux == follow) ? root : aux; ////
Q.push_back(follow);
}
}
}
void reset() {
for (int let = 0; let < alphabetSize; ++let) {
if (root->nxt[let] != root) {
dfsReset(root->nxt[let]);
}
}
root->num = 0;
}
void dfsReset(trieNode* node) {
node->num = 0;
for (int let = 0; let < alphabetSize; ++let) {
if (node->nxt[let] != nullptr) {
dfsReset(node->nxt[let]);
}
}
}
void dfsDestruct(trieNode* node) {
for (int let = 0; let < alphabetSize; ++let) {
if (node->nxt[let] != nullptr) {
dfsDestruct(node->nxt[let]);
}
}
delete node;
}
public:
~ahoCorasick() {
for (int let = 0; let < alphabetSize; ++let) {
if (root->nxt[let] != root) {
dfsDestruct(root->nxt[let]);
}
}
delete root;
}
};
using namespace std;
int main() {
cin.sync_with_stdio(false);
cin.tie(0);cout.tie(0);
string text;
in >> text;
int N;
in >> N;
vector<string> dict(N);
for (string& word : dict) {
in >> word;
}
ahoCorasick ac(dict);
vector<int> occ;
ac.getNumberOfOccurences(text + text + "sadasdaaaaaaabbbbbbbbbaaaaaaabsadasdaaweqrdtgfdg" + text, occ); // test daca reset functioneaza;
ac.getNumberOfOccurences(text, occ);
for (int o : occ) {
out << o << '\n';
}
return 0;
}