Tire(字典树)
Tire
字典树,又称为单词查找树,Tire 树,是一种树形结构,它是哈希树的变种。
实现原理:
字典树与字典很相似,当要查一个单词是不是在字典树中,首先看单词的第一个字母是不是在字典的第一层,如果不在,说明字典树里没有该单词,如果在就在该字母的孩子节点里找是不是有单词的第二个字母,没有说明没有该单词,有的话用同样的方法继续查找,以此类推。
此算法的核心思想是以空间换时间,利用字符串的公共前缀来减少无谓的字符串比较以达到提高查询效率的目的,其查找的时间复杂度是O(1)。
性质:
1、根节点不包含字符,除根节点以外每个节点只包含一个字符。
2、从根节点到某一个节点,路径i上经过的字符连接起来,为该节点对应的字符串。
3、每个节点的所用子节点包含的字符串不相同。
建树和查询:
1、建树:建树的话,比较简短,就是每个结点有26个子节点,对应的就是26个小写字母,然后依次遍历这个字符串,就能建立一个树,有一个地方要注意的就是这最后一个结点那里,需要标记一下,证明这个是某一个字符串的结尾。
2、查询:查询的话,就更为简单了,就是从根节点依次往下查询,对应的字符是否为空,为空的话,就证明这个字符串在树中不存在,否则,就继续遍历下取,等字符串全部遍历完后,就判断当前指针所指向的位置是否有结束标志,有的话,便是该字符串存在,否则便是不存在。
附上一个水题理解一下代码怎么敲:
统计难题
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131070/65535 K (Java/Others)
Total Submission(s): 66368 Accepted Submission(s): 22892
注意:本题只有一组测试数据,处理到文件结束.
band
bee
absolute
acm
ba
b
band
abc
3
1
0
#include <iostream>
#include <cstdio> using namespace std; int tire[][];
int sum[];
int tot = ; //此处可以理解为层次,就是想当于,每一层数组表示一个指针 void insert(string str) {
int root = ;
int len = str.size();
for(int i = ; i < len; i++) {
int idx = str[i] - 'a';
if(tire[root][idx] == ) {
tire[root][idx] = ++tot;
}
root = tire[root][idx];
sum[root]++;
}
} int query(string str) {
int len = str.size();
int root = ;
for(int i = ; i < len; i++) {
int idx = str[i] - 'a';
if(tire[root][idx] == ) {
return ;
}
root = tire[root][idx];
}
return sum[root];
} int main() {
string str;
while(getline(cin, str)) {
if(str == "") {
break;
}
insert(str);
}
while(cin >> str) {
cout << query(str) << endl;
}
return ;
}
最新文章
- 如何给SVG填充和描边应用线性渐变
- 本机,同机房,同城,异地,不同城,腾讯云ping延时值
- [cb]ScriptableObject 序列化
- JS中javascript:void(0)真正含义
- for each 循环
- 在AWS上安装laravel框架
- Markdown中实现缩进的方法
- 文艺编程 Literate Programming
- java设计模式(1)
- 微信开发之获取jsapi_ticket
- Scrapy 1.4 文档 04 例子
- MVC设计思想
- ES6参数默认值
- html2canvas的踩坑之路
- CentOS SVN服务器管理多项目
- lazarus汉化
- Hibernate(二)持久化对象的状态
- mongodb/python3.6/mysql的安装
- Swift3 获取版本号,比较版本大小
- [T-ARA][거짓말(Part.1)][谎言(Part.1)]
热门文章
- (模拟)关于进制的瞎搞---You Are Given a Decimal String...(Educational Codeforces Round 70 (Rated for Div. 2))
- composer命令介绍之install和update及其区别
- GitHub从小白到熟悉<;五>;
- mysql转换表的存储引擎方法
- Codeforces 1201C. Maximum Median
- CF407D Largest Submatrix 3
- spring基于注解的IoC以及IoC的案例
- vscod插件
- Reducing Snapshots to Points: A Visual Analytics Approach to Dynamic Network Exploration
- 富文本编辑器--获取JSON