// Created by Vladimir Tsvetkov on 08/07/14.
//clear && clear && g++ -o search -std=c++11 -g search.cpp ./../../src/string/unistring.cpp

#include <iostream>
#include <string>
#include <set>
#include <map>
#include "../../include/string/unistring.h"

class trieNode
{
    public:
        Unistring data;
        std::map<Unistring, trieNode> leaves;
        bool isFinal;
        trieNode();
        trieNode(Unistring ndata, std::map<Unistring, trieNode> nleaves);
        ~trieNode();
};

class Trie
{
    public:
        trieNode root;
        Trie();
        ~Trie();
        std::set<Unistring> searchWordsFromTrie(Unistring pattern);
        std::set<Unistring> searchWords(trieNode node, Unistring pattern, int curIndex, Unistring formedString);
};

std::set<Unistring> Trie::searchWordsFromTrie(Unistring pattern)
{
    Unistring word;
    std::set<Unistring> finalset = searchWords(root, pattern, 0, word);
}

int commonPrefix(Unistring data, Unistring pattern, int curIndex)
{
    Unistring cutPattern = *pattern.substr(curIndex);
    for(int i = 0; i < data.size(); i++)
        if (i == cutPattern.size() || data[i] != cutPattern[i])
            return i;
    return data.size();
}

std::set<Unistring> Trie::searchWords(trieNode node, Unistring pattern, int curIndex, Unistring formedString)
{
    std::cout << "searchWordsCall with curIndex " << curIndex << "\n";

    if (node.isFinal && curIndex == (pattern.size() - 1))
    {
        std::set<Unistring> wordSet;
        wordSet.insert(formedString);
        return wordSet;
    }

    std::set<Unistring> wordSet;
    Unistring curChar = *pattern.substr(curIndex, curIndex + 1);

    if (curChar.compare_to())
    {
        Unistring newformedString = formedString;
        wordSet.insert(searchWords(node, pattern, curIndex + 1, newformedString));
        for(auto i:node.leaves)
        {
            Unistring newnewformedString = formedString;
            wordSet.insert(searchWords(i.second, pattern, curIndex, newnewformedString));
        }
        return wordSet;
    } else
    {
        int commonPrefixsize = commonPrefix(node.data, pattern, curIndex);
        //Unistring commonPrefix = node.data.substring(0, commonPrefixsize);
        trieNode nextNode;
        if (commonPrefixsize == node.data.size())
        {
            //поиск от ребенка
            nextNode = node.leaves[pattern[commonPrefixsize]];
        } else
        {
            //сплитим ноду
            Unistring newData = node.data.substr(commonPrefixsize);
            std::map<Unistring, trieNode> newleaves = node.leaves;
            nextNode = trieNode(newData, newleaves);
        }
        wordSet.insert(searchWords(nextNode, pattern, curIndex + commonPrefixsize, formedString + node.data));
        return wordSet;
    }
}

Unistring c_str_to_Unistring(std::string str)
{
  Utf8String strseq = Utf8String((char*)strseq)
}

void test()
{
  std::set<Unistring> resultset;
  //Unistring pattern = "ab*ra*";
  std::string pattern;
  std::cin >> pattern;
  //std::cout << "pattern:\n" << pattern << "\n";
  Utf8String patternseq = Utf8String((char*)pattern.c_str());
  Unistring patternunistring = Unistring(patternseq);
  std::cout << "pattern:\n";
  patternunistring.print();
  std::cout << "\n";
  Unistring *substr = patternunistring.substr(0, 2);
  substr->print();
  //resultset.insert(pattern);
  //Trie trie;
  //resultset = trie.searchWordsFromTrie(pattern);

  //for(auto i:resultset)
    //std::cout << i;
}

int main(int argc, const char * argv[])
{
  test();
  return 0;
}