Trie树 模板（C++)

模板（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;
}