Seminar12

#include <iostream>
#include <string>
#include <unordered_set>
#include <vector>

std::vector<int> OddPalindroms(const std::string& s) {
  std::vector<int> data(s.size(), 1);
  int big_index = 0;
  for (int i = 1; i < s.size(); ++i) {
    if (i < big_index + data[big_index] - 1)
      data[i] = std::min(data[2 * big_index - i], big_index + data[big_index] - i);
    for (int j = data[i]; i - j >= 0 && i + j < s.size() && s[i - j] == s[i + j]; ++j) ++data[i];
    if (i + data[i] > big_index + data[big_index]) big_index = i;
  }
  return data;
}

int main0() {
  std::string s;
  std::cin >> s;
  std::vector<int> odd_palindroms = OddPalindroms(s);
  for (int v : odd_palindroms) std::cout << v << " ";
  return 0;
}

struct Node {
//  char Letter = 0;  // Буква, по которой пришли в узел.
  bool IsTerminal = false;
  std::vector<Node*> Children;

  ~Node() { for(auto x : Children) delete x; }
};

// Children [0, 1, 2, 3, 4, 5, 6, 7, ..., 32, ..., 48, 49, ... ]
//                                        ' '          '1'
//                                        nullptr     Node*

class Trie {
 public:
  ~Trie() { delete start; }
  void Add(const std::string& s);
  void Print() const;

 private:
  Node* start = new Node;
  void DFSPrint(std::string& s, Node* current) const;
};

// hello
// hell
void Trie::Add(const std::string& s) {
  Node* cur_node = start;
  for (int i = 0; i < s.size(); ++i) {
    if (cur_node->Children.empty()) cur_node->Children.assign(256, nullptr);
    if (!cur_node->Children[s[i]]) {
      cur_node->Children[s[i]] = new Node;
    }
    cur_node = cur_node->Children[s[i]];
    cur_node->IsTerminal |= (i == s.size() - 1);
  }
}

void Trie::Print() const {
  std::string s;
  DFSPrint(s, start);
}

void Trie::DFSPrint(std::string& s, Node* current) const {
  if (current->IsTerminal) std::cout << s << "\n";
  for (int i = 0; i < current->Children.size(); ++i) {
    if (current->Children[i]) {
      s.push_back(char(i));
      DFSPrint(s, current->Children[i]);
      s.pop_back();
    }
  }
}

int main1() {
  Trie trie;
  int n = 0; std::cin >> n;
  for (int i = 0; i < n; ++i) {
    std::string s;
    std::cin >> s;
    trie.Add(s);
  }
  trie.Print();
  return 0;
}

int main() {
  std::unordered_set<int> x;
  x.insert(3);
  std::cout << x.bucket_count();
  return 0;
}