Seminar12

#include <iostream>
#include <map>
#include <string>
#include <vector>

std::vector<int> ManacherOdd(const std::string& s) {
  std::vector<int> result(s.size(), 1);
  int l = 0, r = 1;
  for (int i = 1; i < s.size(); ++i) {
    // TODO: Сделать отдельную переменную для result[i].
    if (i < r) {
      int sym_index = l + r - i - 1;
      result[i] = std::min(result[sym_index], r - i);
    }
    while (i + result[i] < s.size() && i - result[i] >= 0 && s[i + result[i]] == s[i - result[i]]) ++result[i];
    if (i + result[i] > r) {
      r = i + result[i];
      l = i - result[i] + 1;
    }
  }
  return result;
}

int main1() {
  std::string s;
  std::cin >> s;
  auto result = ManacherOdd(s);
  for (int x : result) std::cout << x << " ";
  std::cout << std::endl;
  return 0;
}

struct Node {
  std::map<char, Node*> Go;
  bool Terminal = false;
};
class Trie {
 public:
  Trie() : root(new Node) {}
  // TODO: Destruct
  void Add(const std::string& s);
  void Print() const { std::string prefix; Print(prefix, root); }
 private:
  Node* root;
  static void Print(std::string& prefix, Node* n);
};
void Trie::Add(const std::string& s) {
  Node* current = root;
  for (char c : s) {
    if (auto it = current->Go.find(c); it != current->Go.end())
      current = it->second;
    else
      current = current->Go[c] = new Node;
  }
  current->Terminal = true;
}

void Trie::Print(std::string& prefix, Node* n) {
  std::cout << prefix << (n->Terminal ? "\t\t - Terminal" : "") << "\n";
  // if (n->Terminal) result.emplace_back(prefix);
  for (auto [c, target] : n->Go) {
    prefix.push_back(c);
    Print(prefix, target);
    prefix.pop_back();
  }
}

int main() {
  Trie t;
  t.Add("arc");
  t.Add("b");
  t.Add("car");
  t.Add("c");
  t.Add("cat");
  t.Print();
  return 0;
}