tire树的存储和并查集
2023-02-18 16:27:26 时间
tire树
tire树又称字典树,是一种能够高效存储和查找字符串集合的数据结构。
图形如下图所示
每个节点表示一个字符串中的字符,从根节点到灰色节点的一条路径表示一个字符串(灰色节点表示是某个单词的结束字符,但不一定都是叶子节点)。这样,我们就可以通过遍历这棵树来检索是否存在待匹配的字符串了。
代码实现
用二维数组来抽象
//Trie树快速存储字符集合和快速查询字符集合
#include <iostream>
using namespace std;
const int N = 100010;
//son[][]存储子节点的位置,分支最多26条;
//cnt[]存储以某节点结尾的字符串个数(同时也起标记作用)
//idx表示当前要插入的节点是第几个,每创建一个节点值+1
int son[N][26], cnt[N], idx;
char str[N];
void insert(char *str)
{
int p = 0; //类似指针,指向当前节点
for (int i = 0; str[i]; i++)
{
int u = str[i] - 'a'; //将字母转化为数字
if (!son[p][u]) son[p][u] = ++idx; //该节点不存在,创建节点
p = son[p][u]; //使“p指针”指向下一个节点
}
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]; //返回字符串出现的次数
}
int main()
{
int m;
cin >> m;
while (m--)
{
char op[2];
scanf("%s%s", &op, &str);
if (*op == 'I') insert(str);
else printf("%d\n", query(str));
}
return 0;
}
并查集
下面我们来下一个知识,并查集,代码虽短,但是有思维
一般是以下用处: 1.将俩个集合合并 2.检查俩个元素是否在一个集合中
并查集在近乎O(1)的时间复杂度内,完成这俩个操作
基本原理: 用一棵树来表示一个集合,其树根就是集合的编号,每个节点存储它的父节点,p[x]即为他的父节点
判断树根if(p[x] == x
求集合编号while(p[x] != x) x = p[x];
合并俩个集合:
1.暴力:将px直接插入到py中,或者将py直接插入到px中,将一个集合看作另一个集合的儿子,插入 2.优化: 找到一个根节点就全部插入,用专业的名词叫做路径压缩
#include<iostream>
using namespace std;
const int N=100010;
int p[N];//定义多个集合
int find(int x)//加路径压缩
{
if(p[x]!=x) p[x]=find(p[x]);
/*
经上述可以发现,每个集合中只有祖宗节点的p[x]值等于他自己,即:
p[x]=x;
*/
return p[x];
//找到了便返回祖宗节点的值
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) p[i]=i;
while(m--)
{
char op[2];
int a,b;
scanf("%s%d%d",op,&a,&b);
if(*op=='M') p[find(a)]=find(b);//集合合并操作
else
if(find(a)==find(b))
//如果祖宗节点一样,就输出yes
printf("Yes\n");
else
printf("No\n");
}
return 0;
}
相关文章
- Java之五种遍历Map集合的方式
- Jmeter扩展组件开发(7) - 自定义java请求的开发
- c字符串详细解析
- 断网了怎么办?那就快去体验【Microsoft Edge浏览器】提供的离线冲浪小游戏~娱乐一下
- 大一学生课设c——服装管理系统
- 1篇文章教会你MarkDown语法,从此开始博客之路
- 蓝桥杯每日一刷(第一天)
- 蓝桥杯每日一刷(第二天)
- 蓝桥杯每日一刷(第三天)
- 二叉树的三种遍历方式
- CONCATENATEX函数的不归路
- 搜索算法dfs和bfs解析(附有例题)
- 蓝桥杯每日一刷(第四天2016)
- 听说你还不会滑动窗口?来一篇文章带你学会滑动窗口算法
- Microsoft VS Code安装教程
- 肝一个周整理Java中容易混淆的基础知识
- ASICS的报表有哪些值得学习的地方?
- 蓝桥杯每日一刷(第六天)——暂会哈希
- 旅行商问题近似解——NP完全问题
- 【DHCP实验】使用三层交换机配置DHCP Server服务器(基于全局地址池配置)