网站主题怎么写,如何优化网站首页,外贸平台有哪些电商,网站开发要学什么语言前言
Trie树大家能够掌握即可#xff0c;其实用到的地方并不多#xff0c;本文将为大家介绍一下。
一、Trie树的基本内容
1、根节点不包含字符#xff0c;除根结点之外每一个结点都只包含一个字符#xff1b; 2、字典树用边表示字母表示 3、从根节点到某一结点#xff… 前言
Trie树大家能够掌握即可其实用到的地方并不多本文将为大家介绍一下。
一、Trie树的基本内容
1、根节点不包含字符除根结点之外每一个结点都只包含一个字符 2、字典树用边表示字母表示 3、从根节点到某一结点 路径上经过的字符连接起来为该结点对应的字符串 4、每个节点的所有子结点包含的字符都不同。每个结点最多有26个子节点(假设给定字符集中包含26个英文字母) 5、有相同前缀的单词共用前缀节点 6、整棵树的根节点是空的便于插入和查找 7、每个单词结束的时候用一个特殊字符表示那么从根节点到任意一个特殊字符所经过的边的所有字母表示一个单词 8、Trie树的空间效率较低实际上是用空间来换时间的一种数据结构
图解 二、典型例题
例1 AC代码
数组
#include iostream
using namespace std;
const int N 100010;
int son[N][26], cnt[N], idx;//下标是0的点,既是根节点,又是空节点
char str[N];//插入操作
void insert(char str[]) {int p 0;//从根节点开始for (int i 0; str[i]; i) {//字符串末尾是0int u str[i] - a;//把小写字母映射成0~25if (!son[p][u])//如果p这个节点不存在u这个儿子,son[p][u] idx;//就把他创建出来p son[p][u];//走到下一个节点}cnt[p];//以这个节点的单词数量多了一个
}//查询
int query(char str[]) {int p 0;//从根节点开始for (int i 0; str[i]; i) {int u str[i] - a;//当前字母对应子节点的编号if (!son[p][u])return 0;p son[p][u];}return cnt[p];//返回以p结尾的单词数量
}int main() {int n;scanf(%d, n);while (n--) {char op[2];scanf(%s%s, op, str);if (op[0] I)insert(str);elseprintf(%d\n, query(str));}return 0;
}
STL
#includeiostream
using namespace std;
#includemap
int n;
char c;
string x;
mapstring,intm;
int main()
{cinn;while(n--){cincx;if(cI)m[x];if(cQ)coutm[x]endl;}return 0;
}
例2 AC代码
#include iostream
#include algorithm
using namespace std;
const int N 100010, M 31 * N;
int son[M][2]; int a[N];
int idx;void insert(int x)
{int p 0; for (int i 30; i 0; i --) {int u x i 1; if (!son[p][u]) son[p][u] idx; p son[p][u]; }
}int query(int x)
{int p 0, res 0; for (int i 30; i 0; i --) {int u x i 1;if (son[p][!u]) {p son[p][!u]; res res * 2 !u; } else{p son[p][u];res res * 2 u;}}return res;
}
int main()
{int n;scanf(%d, n); for (int i 0; i n; i ) scanf(%d, a[i]);int res 0;for (int i 0; i n; i ){insert(a[i]);int t query(a[i]); res max(res, a[i] ^ t);}printf(%d\n, res);return 0;}
总结
这部分不是很难理解大家熟练掌握即可感谢大家的观看谢谢大家
