字典树 模板(C++)"/>
Trie字典树 模板(C++)
Trie树 介绍:
Trie树(也称为前缀树或字典树)是一种特殊的树数据结构,通常用于处理字符串数据,特别是用于高效地存储、检索和搜索大量字符串数据集。
Trie树中有两个操作,一个是插入(insert),一个是查询(query)。
给出Trie树模板,包含详细的注释。
Trie树 模板:
#include<iostream>
#include<string>using namespace std;const int N = 1000010;int son[N][26], cnt[N], idx;// 存树,相当于图论中e,ne数组两个一维和起来了,(因为26个高效利用,浪费少)cnt记录某个节点为结尾的字符串个数
// idx 索引位置,与图论中相似,0 位置是整个树的树根(没有值,就是查询起点),也表示 空节点void insert(string str) {int p = 0; // 树根for (int i = 0; i < str.size(); i++) {int t = str[i] - 'a'; // 该字符对应的ASCII码if (!son[p][t]) son[p][t] = ++idx; // 若此节点没有值,给此节点赋值(索引)p = son[p][t]; // 在树中向下寻找,相当于进入下一层}cnt[p]++; // 一此节点为结尾的 计数++
}// 查询与插入相似的过程
int query(string str) {int p = 0;for (int i = 0; i < str.size(); i++) {int t = str[i] - 'a';if (!son[p][t]) return 0; // 查找不到,说明没有,返回 0p = son[p][t];}return cnt[p];
}int main() {int n; // 要插入和查询的字符串个数cin >> n;while(n--) {char op; // 要进行的操作,I 插入,Q 查询字符串个数string str;cin >> op >> str;if (op == 'I') insert(str); // 插入else cout << query(str) << endl; // 寻找}return 0;
}
更多推荐
Trie字典树 模板(C++)
发布评论