/*
	в 3-Е дереве найти все слова, содержащащие только указанные буквы
*/

#include "pch.h"
#include <iostream>
#include <string>
#include <vector>
using namespace std;

#define char_int(c) ((int)c - (int)'a')
#define int_to_char(c) ((char)c + (char)'a')
#define SIZE (26)


struct Trie
{
	Trie *child[SIZE];
	bool end;
};

Trie *getNode()
{
	Trie *newNode = new Trie;
	newNode->end = false;
	for (int i = 0; i < SIZE; i++)
		newNode->child[i] = NULL;
	return newNode;
}

void insert(Trie *root, char *Key)
{
	int n = strlen(Key);
	Trie *pChild = root;

	for (int i = 0; i < n; i++)
	{
		int index = char_int(Key[i]);

		if (!pChild->child[index])
			pChild->child[index] = getNode();

		pChild = pChild->child[index];
	}

	pChild->end = true;
}

void searchWord(Trie *root, bool Hash[], string str)
{	if (root->end == true)
		cout << str << endl;

	for (int K = 0; K < SIZE; K++)
	{
		if (Hash[K] == true && root->child[K])
		{
			char c = int_to_char(K);
			searchWord(root->child[K], Hash, str + c);
		}
	}
}

void PrintAllWords(char Arr[], Trie *root, int n)
{
	bool Hash[SIZE];

	for (int i = 0; i < n; i++)
		Hash[char_int(Arr[i])] = true; // хранит символы, для которых нужно найти слова

	Trie *pChild = root;

	string str = "";

	for (int i = 0; i < SIZE; i++)
	{

		if (Hash[i] == true && pChild->child[i])
		{
			str = str + (char)int_to_char(i);
			searchWord(pChild->child[i], Hash, str);
			str = "";
		}
	}
}


int main()
{
	char Dict[][20] = { "go", "bat", "me", "eat",
					   "goal", "boy", "run"};

	Trie *root = getNode();
	int n = sizeof(Dict) / sizeof(Dict[0]);
	for (int i = 0; i < n; i++)
		insert(root, Dict[i]);
	char arr[] = { 'e', 'o', 'b', 'a', 'm', 'g', 'l','h' };
	int N = sizeof(arr) / sizeof(arr[0]);
	PrintAllWords(arr, root, N);
	return 0;
}