#include <algorithm>
#include <vector>
#include <string>
#include <memory>
#include <cassert>
#include <iostream>

class PrefixNode {
  // TODO: replace with more efficient data structure for lookup
  using children_t = std::vector<std::unique_ptr<PrefixNode>>;
  char Letter;
  bool Terminator { false };
  children_t Children;
public:
  PrefixNode(char letter);
  // \brief add new children if \p letter doesn't exist.
  // \return pointer to the node with \p letter.
  PrefixNode *addChildren(char letter);
  PrefixNode *hasChildren(char letter) const;
  // \brief mark the Node as last character of a word
  void endOfWord() { Terminator = true; }
  bool isTerminator() const { return Terminator; }
};

class Dictionary {
  PrefixNode Root;
public:
  Dictionary() : Root{'\0'} {}
  bool exist(const std::string& word) const ;
  void add(const std::string& word);
};

PrefixNode::PrefixNode(char letter) : Letter{ letter }, Children(26) {}

// We assume we have 26 preallocated default constructed children
PrefixNode *PrefixNode::addChildren(char letter) {
  assert(letter >= 'a' && letter <= 'z' && "Non letter character");
  auto& letterNode = Children[letter - 'a'];
  if (!letterNode)
    letterNode.reset(new PrefixNode(letter));
  return letterNode.get();
}

PrefixNode *PrefixNode::hasChildren(char letter) const {
  assert(letter >= 'a' && letter <= 'z' && "Non letter character");
  return Children[letter - 'a'].get();
}

void Dictionary::add(const std::string& word) {
  PrefixNode *currentNode { &Root };
  for (auto letter : word) {
    currentNode = currentNode->addChildren(letter);
  }
  currentNode->endOfWord();
}

bool Dictionary::exist(const std::string& word) const {
  const PrefixNode *currentNode { &Root };
  for (auto letter : word) {
    currentNode = currentNode->hasChildren(letter);
    if (!currentNode)
      return false;
  }
  return currentNode->isTerminator();
}

void readWordsFromStdin(Dictionary& dictionary) {
  std::string word;
  while (std::cin >> word) {
    if (word.empty())
      break;
    dictionary.add(word);
  }
}