字典树介绍
字典树（Trie，前缀树或单词查找树）是一种多叉树形数据结构，专门用于高效存储和检索字符串（或有序序列） 的前缀、完整序列。其核心设计思想是利用数据的公共前缀共享存储路径，从而减少空间浪费，并将插入、查询的时间复杂度降低到与序列长度相关的水平（O(L)，L为序列长度），在字符串处理场景中具有不可替代的优势。
核心思想
在处理大量字符串时，若直接存储每个字符串，会存在大量重复前缀的冗余（比如
apple、app、apply都共享app前缀）。字典树通过让拥有相同前缀的字符串共享同一部分路径，将冗余的前缀合并，从而实现空间和时间的优化。比如插入字符串单"abc",“abb”,“bca”,"bc"。红点代表有一个以此节点为终点的单词。
然后，我们如果要查找某个单词如s=“abc”,就可以这样
构建字典树
int id = 0; // 节点计数器：为新建节点分配唯一编号（根节点固定为0） int cnt[N]; // cnt[p]：以节点p对应的前缀的模式串数量（核心统计值） unordered_map<int, int> node[N]; // 每个节点的子节点映射：// node[p]是哈希表，键=字符转换后的索引，值=子节点编号插入模式串以构建字典树
void insert(string s){int p = 0; // 从根节点（编号0）开始遍历for(int i = 0; i < s.size(); ++i){ // 遍历字符串的每个字符int t = change(s[i]); // 字符转索引if(node[p][t] == 0){ // 若当前节点p的t字符对应的子节点不存在id++; // 新建节点，编号自增node[p][t] = id; // 记录子节点编号}p = node[p][t]; // 移动到子节点cnt[p]++; // 该前缀的模式串数量+1} }在字典树上查找文本串
int find(string s){int p = 0; // 从根节点开始遍历for(int i = 0; i < s.size(); ++i){ // 遍历查询字符串的每个字符int t = change(s[i]); // 字符转索引if(node[p].count(t) == 0) return 0; // 子节点不存在，返回0p = node[p][t]; // 移动到子节点}return cnt[p]; // 返回该前缀的模式串数量 }
例题：【模板】Trie 字典树_牛客题霸_牛客网
代码通过change函数实现了大小写字母均支持的字典树
const int N = 1e5 + 5; int id = 0; int cnt[N]; unordered_map<int, int> node[N];int change(char c){if(c >= 'a' && c <= 'z') return c - 'a';if(c >= 'A' && c <= 'Z') return 26 + c - 'A';return -1; }void insert(string s){int p = 0;for(int i = 0; i < s.size(); ++i){int t = change(s[i]);if(node[p][t] == 0){id++;node[p][t] = id;}p = node[p][t];cnt[p]++;} }int find(string s){int p = 0;for(int i = 0; i < s.size(); ++i){int t = change(s[i]);if(node[p].count(t) == 0) return 0;p = node[p][t];}return cnt[p]; }void solve(){int n, q;string s, t;cin >> n >> q;for(int i = 0; i < n; ++i){cin >> s;insert(s);}while(q--){cin >> t;cout << find(t) << endl;} }