#include <iostream>
#include <deque>
#include <algorithm>
using namespace std;

#define MAXCHILDS  26
/*
struct Nod { int nr, word_length; string replace_word; Nod* adr[MAXCHILDS]; Nod* failNode; };

Nod _root;

void init(Nod  *x)
{
	x->nr = 0;
	x->failNode = NULL;
	x->word_length = 0;

	for (int i = 0; i < MAXCHILDS; i++)
	{
		x->adr[i] = NULL;
	}
}

void addWord(const string& w, string replace_w)
{
	if (w.length() > 0)
	{
		Nod *currentNod = &_root;
		for (int i = 0; w[i] != 0; i++)
		{
			if (currentNod->adr[w[i] - 0] == NULL)
			{
				currentNod->adr[w[i] - 0] = new Nod;
				init(currentNod->adr[w[i] - 0]);
			}

			currentNod = currentNod->adr[w[i] - 0];
		}
		currentNod->word_length = w.length();

		currentNod->replace_word = replace_w;

		currentNod->nr++;
	}
}

string getReplaceWord(const string& w)
{
	Nod *currentNod = &_root;
	for (int i = 0; w[i] != 0; i++)
	{
		if (currentNod->adr[w[i] - 0] == NULL)
		{
			return string();
		}

		currentNod = currentNod->adr[w[i] - 0];
	}

	return (currentNod->nr > 0) ? currentNod->replace_word : string();
}


bool eraseWord(const string& w)
{
	if (w.length() > 0)
	{
		Nod *currentNod = &_root;
		for (int i = 0; w[i] != 0; i++)
		{
			if (currentNod->adr[w[i] - 0] == NULL)
			{
				return false;
			}

			currentNod = currentNod->adr[w[i] - 0];
		}

		currentNod->nr--;
		currentNod->failNode = NULL;
		return true;
	}
	else
	{
		return false;
	}
}

int numberOfAparitions(const string& w)
{
	if (w.length() > 0)
	{
		Nod *currentNod = &_root;

		for (int i = 0; w[i] != 0; i++)
		{
			if (currentNod->adr[w[i] - 0] != NULL)
			{
				currentNod = currentNod->adr[w[i] - 0];
			}
			else
			{
				return 0;
			}
		}
		return currentNod->nr;
	}
	else
	{
		return 0;
	}
}


/*
	closest ancestor starting at the fail node that has a child with this caracter
	Breadh first
*/
/*
void buildFailSuffixes()
{
	_root.failNode = &_root;
	Nod *currentNode = &_root;


	std::deque<Nod*> deq;
	for (int i = 0; i < MAXCHILDS; i++)
	{
		if (currentNode->adr[i] != NULL)
		{
			currentNode->adr[i]->failNode = &_root;
			deq.push_back(currentNode->adr[i]);
		}
	}

	while (!deq.empty())
	{
		currentNode = deq.front();
		deq.pop_front();

		for (int i = 0; i < MAXCHILDS; i++)
		{
			if (currentNode->adr[i] != NULL)
			{
				deq.push_back(currentNode->adr[i]);

				if (currentNode->failNode->adr[i] != NULL)
				{
					currentNode->adr[i]->failNode = currentNode->failNode->adr[i];
				}
				else
				{
					currentNode->adr[i]->failNode = currentNode->failNode;
				}
			}
		}
	}
}



bool extractWords(const string& line, string& word, string& replace_word)
{
	int count = std::count(line.begin(), line.end(), '@');
	if (count < 4)
	{
		return false;
	}

	int start = line.find('@') + 1;
	int end = line.find('@', start);
	replace_word = line.substr(start, end - start);

	start = line.find('@', end + 1) + 1;
	end = line.find('@', start);
	word = line.substr(start, end - start);

	return true;
}

void build(const std::string& input_path)
{
	bool result;

	std::ifstream fin(input_path);
	string word;
	string replace_word;
	std::string line;
	while (!fin.eof())
	{
		//printProgress(fin.tellg(), fileSize);
		std::getline(fin, line);
		result = extractWords(string(line.c_str()), word, replace_word);
		if (result == true)
		{
			addWord(word, replace_word);
		}
	}

	//printProgress(fin.tellg(), fileSize);

	buildFailSuffixes();
}

void replaceWords(const std::string& input_path, const std::string& output_path)
{
	unsigned char ch;
	std::deque<unsigned char> buffer;

	Nod* currentNode = &_root;

	std::ifstream fin(input_path);
	std::ofstream fout(output_path);

	while (!fin.eof())
	{
		ch = fin.get();
		if (fin.eof())
		{
			break;
		}

		while (currentNode->adr[ch - 0] == NULL)
		{
			if ( currentNode != &_root)
			{
				currentNode = currentNode->failNode;

				fout << currentNode->replace_word.toConstCharString();

                if (currentNode->adr[ch - 0] != NULL)
                {
                    break;
                }

			}
			else
			{
				break;
			}
		}

		if (currentNode->adr[ch - 0] != NULL)
		{
			currentNode = currentNode->adr[ch - 0];
		}

		if (currentNode->word_length != 0)
		{
			fout << currentNode->replace_word.toConstCharString();
		}
	}

	fin.close();
	fout.close();
}


*/

int main()
{
    string input_path = "ahocorasick.in";
    string output_path = "ahocorasick.out";
    //replaceWords(const input_path, const output_path);

//	init(&_root);
    return 0;
}