Trie 树
Trie 树是用来快速存储和查找字符串集合的数据结结构
模板题 835. Trie 字符串统计 - AcWing 题库
#include<iostream> using namespace std; const int NN=100010; int son[NN][26], cnt[NN], idx; int n; string op, s; void insert(const string& str){ int p=0; // 以0号点为根结点 for(int i=0;str[i];i++){ int u=str[i]-'a'; if(son[p][u]==0){ son[p][u]=++idx; } p=son[p][u]; // p 指针向下移动指针向下 } cnt[p]++; // 对字符串的末尾作一个标记, 进行计数 } int query(const string& str){ int p=0; for(int i=0;str[i];i++){ int u=str[i]-'a'; if(son[p][u]==0) // 一旦有一个点没有找到, 则说明就是没有 return 0; p=son[p][u]; } return cnt[p]; } int main(){ int n; cin>>n; for(int i=0;i<n;i++){ cin>>op>>s; if(op[0]=='I'){ insert(s); }else{ cout<<query(s)<<endl; } } return 0; }
并查集
并查集支持如下操作:
- 将两个集合合并
- 查询两个元素是否在同一个集合当中
并查集中每个集合用一棵树进行实行, 每个集合的编号就是树中根结点的编号, 每个结点存储它的父结点, p[x] 表示 x 的父结点
- 判断树根 :
if(p[x]==x) - 求
x的集合编号 : `while(p[x]!=x) x=p[x]; - 合并两个集合 :
p[x]=y
模板题 836. 合并集合 - AcWing 题库
#include<iostream> using namespace std; const int NN=1e5+10; int n,m; string op; int a,b; int p[NN]; // 寻找根节点, 也就是 u 所在的集合编号 int find(int u){ if(p[u]!=u){ p[u]=find(p[u]); // 路径压缩 } return p[u]; } int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ p[i]=i; } for(int i=0;i<m;i++){ cin>>op>>a>>b; if(op[0]=='M'){ p[find(a)]=find(b); // a 的根节点的父节点置成 b 的父节点, 则完成了集合合并 } else{ if(find(a)==find(b)){ cout<<"Yes"<<endl; }else{ cout<<"No"<<endl; } } } return 0; }
