string/trie_map.hpp

• View this file on GitHub
• Last update: 2023-08-19 23:11:08+09:00
• Include: #include "string/trie_map.hpp"

Code

template <typename CHAR>
struct Trie {
  using MP = map<CHAR, int>;
  int n_node;
  vector<MP> TO;
  vector<int> PAR;
  vector<int> BFS;
  vector<int> FAIL;

  Trie() : n_node(1), TO({MP()}), PAR({-1}) {}

  template <typename STRING>
  int add(STRING S) {
    int v = 0;
    for (auto&& s: S) {
      if (!TO[v].count(s)) {
        TO[v][s] = create_node();
        PAR[TO[v][s]] = v;
      }
      v = TO[v][s];
    }
    return v;
  }

  int create_node() {
    TO.eb(MP());
    PAR.eb(-1);
    return n_node++;
  }
};

#line 1 "string/trie_map.hpp"
template <typename CHAR>
struct Trie {
  using MP = map<CHAR, int>;
  int n_node;
  vector<MP> TO;
  vector<int> PAR;
  vector<int> BFS;
  vector<int> FAIL;

  Trie() : n_node(1), TO({MP()}), PAR({-1}) {}

  template <typename STRING>
  int add(STRING S) {
    int v = 0;
    for (auto&& s: S) {
      if (!TO[v].count(s)) {
        TO[v][s] = create_node();
        PAR[TO[v][s]] = v;
      }
      v = TO[v][s];
    }
    return v;
  }

  int create_node() {
    TO.eb(MP());
    PAR.eb(-1);
    return n_node++;
  }
};

Back to top page