Cod sursa(job #1697264)

Utilizator cosmin.pascaruPascaru Cosmin cosmin.pascaru Data 1 mai 2016 12:57:26
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.4 kb
#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 != root_ && !nowFail->next_[i])
				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;
}