字典树

struct Trie {
  static const int N = 5e5 + 5;
  static const int tot = 26;
  int tr[N][tot];
  bool e[N];
  int cnt = 0;

  Trie() {

  }

  Trie(int n) {
    init(n);
  }

  void init(int n) {
    for (int i = 0; i <= n; i++) {
      for (int j = 0; j < tot; j++) {
        tr[i][j] = 0;
      }
      e[i] = 0;
    }
  }

  void add(string &s, char offset = 'a') {
    int p = 1;
    for (int i = 0; i < s.size(); i++) {
      int nex = s[i] - 'a';
      if (!tr[p][nex]) tr[p][nex] = ++cnt;
      p = tr[p][nex];
    }
    e[p] += 1;
  }

  int query(string &s, char offset = 'a') {
    int p = 1;
    for (int i = 0; i < s.size(); i++) {
      int nex = s[i] - 'a';
      if (tr[p][nex] == -1) return false;
      p = tr[p][nex];
    }
    return e[p];
  }
};