简介

又称Trie树，顾名思义，长得像字典的树。

基本思想

维护一棵带有边权的树，以解决字符串相关问题。

例题

【模板】字典树

模板代码

int nex[3000003][75], cnt=0;
// 插入
auto ins = [&](std::string s) -> void {
  int nod = 0;
  for(int i = 0; i < s.size(); ++i) {
    int c = s[i] - '0';
    if(!nex[nod][c]) 
      nex[nod][c] = ++cnt;
    nod = nex[nod][c];
  }
};
// 查询
auto fin = [&](std::string s) -> bool {
  int nod = 0;
  for(int i = 0; i < s.size(); ++i) {
    int c = s[i] - '0';
    if(!nex[nod][c]) 
      return 0;
    nod = nex[nod][c];
  }
  return 1;
};