#pragma once
#include <iostream>
#include <string>
using namespace std;

class trie
{
private:
	class node
	{
	public:
		bool marked;
		node* children[256];

		node()
		{
			marked = false;
			for (int i = 0; i < 256; i++)
				children[i] = nullptr;
		}
	};

	node* root;

	//Print all strings in trie rooted at p
	//with pref attached to the front of them.
	void print(node* p, string pref)
	{
		if (p == nullptr) //base case
		{
			//don't do anything, nothing to print
		}
		else //recursive case
		{
			if (p->marked)
				cout << pref << endl;
			for (int i = 0; i < 256; i++)
				print(p->children[i], pref + (char)i);
		}
	}

public:
	trie()
	{
		root = new node;
	}

	void insert(string s)
	{
		node* arrow = root;

		for (int i = 0; i < s.size(); i++)
		{
			if (arrow->children[s[i]] == nullptr)
				arrow->children[s[i]] = new node;

			arrow = arrow->children[s[i]];
		}
		arrow->marked = true;
	}

	void printAll()
	{
		print(root, "");
	}
};