Seminar13

#include <iostream>
#include <map>
#include <memory>
#include <unordered_map>
#include <vector>

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

void Trie::Print(std::string& prefix, const std::unique_ptr<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 main1() {
  Trie t;
  t.Add("arc");
  t.Add("b");
  t.Add("car");
  t.Add("c");
  t.Add("cat");
  t.Print();

  std::cout << sizeof(std::unique_ptr<Node>) << std::endl;
  return 0;
}

class OrdString {
  size_t capacity;
  char* buf;
  size_t size;
};

class OptString {
  size_t capacity;

  union {
    struct {
      char* buf;
      size_t size;
    } heapbuf;

    char stackbuf[sizeof(heapbuf)];
  };
};

int main2() {
  std::cout << sizeof(OrdString) << std::endl;
  std::cout << sizeof(OptString) << std::endl;
  std::cout << sizeof(std::string) << std::endl;
  int min_cap = (sizeof(OrdString) - 1)/sizeof(char) > 2 ?
              (sizeof(OrdString) - 1)/sizeof(char) : 2;
  std::cout << min_cap << std::endl;
  return 0;
}

struct ACNode {
  char in_symbol;  // 1
  bool is_terminal;  // 1 + 2
  int parent;  // 4
  int suffix_link = -1;  // 4 + 4
  std::unordered_map<char, int> go;  // 40. Сохраненные переходы по символам из текста + Переходы по букве исходные
};

int main() {
  ACNode n;
  std::cout << sizeof(n) << std::endl;
  return 0;
}
class AhoCorasik {
 public:
  explicit AhoCorasik(std::vector<std::string>& patterns);

 private:
  std::vector<ACNode> nodes;

  int GoTo(int nodeid, char symbol);
  int Suffix(int nodeid);
};

int AhoCorasik::GoTo(int nodeid, char symbol) {
  ACNode& node = nodes[nodeid];
  if (auto it = node.go.find(symbol); it != node.go.end()) return it->second;
  return node.go[symbol] = GoTo(Suffix(nodeid), symbol);
}

int AhoCorasik::Suffix(int nodeid) {
  ACNode& node = nodes[nodeid];
  if (node.suffix_link >= 0) return node.suffix_link;
  return node.suffix_link = GoTo(Suffix(node.parent), node.in_symbol);
}