Trie(字典树)
2024-09-03 23:35:35
没时间整理了,老吕又讲课了@ @
概念
Trie即字典树,又称单词查找树或键树,是一种树形结构,是一种哈希树的变种,典型应用是统计和排序大量的字符串(不限于字符串)
Trie字典树主要用于存储字符串,Trie 的每个 Node 保存一个字符。用链表来描述的话,就是一个字符串就是一个链表。每个 Node 都保存了它的所有子节点。
基本操作
插入 查找 前缀查询 删除
实质:空间换时间
eg:
插入单词:a,ab,abc,abd,acb
瞅个板子
给定 \(n\) 个长度不超过 \(10\) 的数字串,问其中是否存在两个数字串 \(S,T\),使得 \(S\) 是 \(T\) 的前缀
hash:时间复杂度起飞
这不显然是字典树的板子么
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <string>
#include <cmath>
#include <map>
using namespace std;
const int A = 1e3 + 2;
const int B = 1e4 + 2;
const int C = 1e5 + 5;
const int D = 2e6 + 5;
const int inf = 0x3f3f3f3f;
const int mod = 99984198447;
int read(){
int x = 0,f = 1;char c = getchar();
while(c < '0'||c > '9'){if(c == '-')f = -1;c = getchar();}
while(c >= '0'&&c <= '9'){x = x*10 + c - '0';c = getchar();}
return x*f;
}
int T, n, tree[C][11],cnt;
bool vis[C],ans;
char s[50];
bool insert(char * s){
int len = strlen(s),u = 1;
bool flag = false;
for(int i = 0;i < len; i++){
int num = s[i] - '0';
if(!tree[u][num])
tree[u][num] = ++cnt;//如果没有这个字母,就新建一个点
else if(i == len - 1) flag = true;//如果单词在字典树中能找到(即字典树中恰好有这个单词)
u = tree[u][num];//从新建的点后者原来的点向下走,继续寻找
if(vis[u])flag = true;//字典中的单词为新填的单词的前缀
}
vis[u] = true;//将单词的最后一个字母在字典树中打上标记
return flag;
}
void clear(){//注意清零
cnt = 1;
memset(vis, 0,sizeof(vis));
memset(tree, 0,sizeof(tree));
ans = false;
}
int main(){
T = read();
while(T--){
n = read();
clear();
for(int i = 1;i <= n; i++){
scanf("%s", s);
if(insert(s))ans = true;
}
if(!ans)printf("YES\n");
else printf("NO\n");
}
}
最新文章
- C#播放MP3源代码
- 东大OJ-Prim算法
- TCP/IP的Socket编程
- Delphi 2009 泛型容器单元(Generics.Collections)[1]: TList<;T>;
- 转载ASP.NET MVC 和ASP.NET Web Form简单区别
- LaTeX手动安装宏包(package)以及生成帮助文档的整套流程
- 【剑指offer】面试题28:字符串的排列
- java发布项目后注意小点,以及对于金额在java中的处理
- Linux中Nginx反向代理下的tomcat集群
- 数据库db2错误代码大全
- Word Press使用
- Java导出freemarker的三种方法
- SVN---搭建幸福之家
- [转]windows中断与共享的连接(samba)
- 自动提取文件系统---binwalk(一)
- vmware centos7 动态ip->;静态
- Sql Server 查询库表记录数
- Linux 系统调整内核参数
- python selenium判断元素是否存在的问题
- WebDav的java客户端开发包:Jackrabbit
热门文章
- 【kinetic】操作系统探索总结(五)创建简单的机器人模型smartcar
- jQuery作业 点击显示
- AOP的姿势之 简化混用 MemoryCache 和 DistributedCache 的方式
- TurtleBot3 Waffle (tx2版华夫)(6)
- 远程分支删除后,git branch -a还能看到的解决方法
- EF Core CodeFirst数据库自动迁移
- phpstorm 注册码破解
- 上班从换一张桌面壁纸开始——开源小工具Bing每日壁纸
- Java 中 Executors.newSingleThreadExecutor() 与Executors.newFixedThreadPool(1)有什么区别
- ICMP协议概述