#include <iostream>
#include <unordered_map>
#include <string>
#include <sstream>
#include <iosfwd>
#include <algorithm>
#include <assert.h>
#include <array>

using TDict = std::unordered_map<std::string, std::string>;
TDict dict = { {"ehllo","hello"}, {"dlorw","world"} };

//////////////////////RECONSTRUCT-EASY///////////

std::string reconstruct(std::string str)
{
    std::string tok, res;
    std::stringstream st(str);

    while (std::getline(st, tok, ' '))
    {
        if (res.size() != 0)
        {
            res += " ";
        }

        std::sort(tok.begin(),tok.end());
        auto iter = dict.find(tok);
        assert(iter != dict.end());
        res += iter->second;
    }

    return res;
}

//////////////////////RECONSTRUCT-HARD///////////

const int azSz = ('z' - 'a') + 1;

struct PrefixNode
{
    std::array<PrefixNode*, azSz> children;
    std::string word;

    PrefixNode* GetChild(char c)
    {
        return children[c - 'a'];
    }

    PrefixNode* GetOrCreateChild(char c)
    {
        if (!GetChild(c))
        {
            children[c - 'a'] = new PrefixNode();
        }

        return GetChild(c);
    }

    PrefixNode()
    {
        children.fill(nullptr);
    }
};

class PrefixTree
{
public:
    PrefixTree(TDict& dict);
    void Insert(const std::string& mangled, const std::string& real);

    bool Reconstruct(const std::string& str, std::string& ret);

private:
    PrefixNode root;
};

PrefixTree::PrefixTree(TDict& d)
{
    for (auto iter = d.begin(); iter != d.end(); ++iter)
    {
        Insert(iter->first, iter->second);
    }
}

void PrefixTree::Insert(const std::string& mangled, const std::string& real)
{
    auto* curr = &root;
    for (auto& c : mangled)
    {
        auto* next = curr->GetOrCreateChild(c);
        if (!next)
        {
            next = new PrefixNode();
        }

        curr = next;
    }

    assert(curr->word.size() == 0);
    curr->word = real;
}

bool PrefixTree::Reconstruct(const std::string& str, std::string& ret)
{
    auto* curr = &root;
    for (auto& c : str)
    {
        auto* next = curr->GetChild(c);
        if (!next)
        {
            return false;
        }

        curr = next;
    }

    if (curr->word.size() == 0)
    {
        return false;
    }

    ret = curr->word;
    return true;
}

std::string reconstructHard(std::string str)
{
    PrefixTree tree(dict);

    std::string buf,fin;

    for (auto& c : str)
    {
        auto iter = std::upper_bound(buf.begin(), buf.end(), c);
        buf.insert(iter, c);
        std::string ret;

        if (tree.Reconstruct(buf, ret))
        {
            buf = "";

            if (fin.size() != 0)
            {
                fin += " ";
            }
            fin += ret;
        }
    }

    return fin;
}

//////////////////////////////////////////////////

int main()
{
    std::cout << reconstruct("helol drowl helol drowl").c_str();
    std::cout << reconstructHard("heloldrowlheloldrowl").c_str();
}