Trie字典树

字典树介绍

字典树（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;}
}