Pagini recente » Cod sursa (job #2903513) | Monitorul de evaluare | Cod sursa (job #1536751) | Rating Stefan (StStefan) | Cod sursa (job #1697262)
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cstring>
#include <queue>
#define DIM_TEXT 1000005
#define NR_PATTERNS 105
#define DIM_PATTERN 100005
#define DIM_ALPHABET 26
using namespace std;
class AhoCorasickNode;
class AhoCorasickTree;
class AhoCorasickNode
{
friend class AhoCorasickTree;
private:
vector<int> ends_;
int nrStops_;
AhoCorasickNode *next_[DIM_ALPHABET];
AhoCorasickNode *fail_;
public:
AhoCorasickNode();
AhoCorasickNode* Next(char c);
AhoCorasickNode* Fail();
};
// AhoCorasickNode implementation
AhoCorasickNode::AhoCorasickNode()
{
nrStops_ = 0;
fail_ = NULL;
memset(next_, 0, sizeof(next_));
}
AhoCorasickNode* AhoCorasickNode::Next(char c)
{
if (next_[c - 'a']) return next_[c - 'a'];
return NULL;
}
AhoCorasickNode* AhoCorasickNode::Fail()
{
return fail_;
}
// AhoCorasickTree definition
class AhoCorasickTree
{
private:
AhoCorasickNode *root_;
vector<AhoCorasickNode*> q_;
vector<AhoCorasickNode*> wordEnds_;
int nrWords_;
bool isFinalized_;
public:
AhoCorasickTree();
void InsertWord(const char*, int);
void FinalizeAutomaton();
vector <int> GetApparitionsCounts(const char*);
};
AhoCorasickTree::AhoCorasickTree()
{
root_ = new AhoCorasickNode;
nrWords_ = 0;
isFinalized_ = false;
}
void AhoCorasickTree::InsertWord(const char* s, int index)
{
char* p = (char*)s;
AhoCorasickNode *currentNode = root_;
while (islower(*p))
{
if (currentNode->next_[*p - 'a'] == NULL)
{ currentNode->next_[*p - 'a'] = new AhoCorasickNode; }
currentNode = currentNode->next_[*p - 'a'];
++p;
}
currentNode->ends_.push_back(index);
++nrWords_;
isFinalized_ = false;
}
void AhoCorasickTree::FinalizeAutomaton()
{
if (isFinalized_) return;
q_.push_back(root_);
root_->fail_ = root_;
int start = 0;
AhoCorasickNode *nowFail;
while (start < q_.size()){
AhoCorasickNode* now = q_[start];
for (int i = 0; i < DIM_ALPHABET; ++i){
if (!now->next_[i])
continue;
nowFail = now->fail_;
while (!nowFail->next_[i] && nowFail->next_[i] != root_)
nowFail = nowFail->fail_;
if (nowFail != now && nowFail->next_[i])
nowFail = nowFail->next_[i];
now->next_[i]->fail_= nowFail;
q_.push_back(now->next_[i]);
}
++start;
}
root_->fail_ = NULL;
isFinalized_ = true;
}
vector<int> AhoCorasickTree::GetApparitionsCounts(const char* s)
{
vector<int> apparitions(nrWords_ + 5);
AhoCorasickNode *now = root_;
for (char* p = (char*)s; *p; ++p) {
while (!now->next_[*p - 'a'] && now != root_)
now = now->fail_;
if (now->next_[*p - 'a'])
now = now->next_[*p - 'a'];
now->nrStops_++;
}
for (int i = q_.size() - 1; i >= 0; --i)
{
if (q_[i]->fail_)
q_[i]->fail_->nrStops_ += q_[i]->nrStops_;
for (auto end : q_[i]->ends_)
apparitions[end] += q_[i]->nrStops_;
}
return apparitions;
}
int main()
{
ios_base::sync_with_stdio(false);
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
char text[DIM_TEXT];
fin >> text;
int n;
fin >> n;
char word[DIM_PATTERN];
AhoCorasickTree automaton;
for (int i = 1; i <= n; ++i)
{
fin >> word;
automaton.InsertWord(word, i);
}
automaton.FinalizeAutomaton();
vector<int> results = automaton.GetApparitionsCounts(text);
for (int i = 1; i <= n; ++i)
fout << results[i] << '\n';
return 0;
}