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

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

		//augmentation:
		string longest;

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

	node* root;

	//print all strings in tree rooted at p
	//with pref stuck to front.
	void display(node* p, string pref)
	{
		if (p == nullptr)
		{
		}
		else
		{
			//possibly print root
			if (p->marked)
				cout << pref << endl;

			//recursively print subtrees
			for (int i = 0; i < 256; i++)
			{
				display(p->children[i], pref + (char)i);
			}
		}
	}

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

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

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

			arrow = arrow->children[s[i]];

			if (s.length() > arrow->longest.length())
				arrow->longest = s;
		}

		arrow->marked = true;
	}

	string badCompletion(string pre)
	{
		node* arrow = root;
		for (int i = 0; i < pre.length(); i++)
		{
			arrow = arrow->children[pre[i]];
			
			if (arrow == nullptr)
				return pre;
		}
		return arrow->longest;
	}

	void display()
	{
		display(root, "");
	}
};