当前位置:   article > 正文

trie树学习笔记&模板&例题_trie树习题

trie树习题

一、tire树

定义:Trie树又称字典树、单词查找树。是一种能够高效存储和查找字符串集合的数据结构。

实现:分为insert(插入),query(查询)操作。

二、

模板 acwingP835:https://www.acwing.com/problem/content/description/837/

插入操作:

  1. void insert(char *str)
  2. {
  3. int p = 0; //类似指针,指向当前节点
  4. for(int i = 0; str[i]; i++)
  5. {
  6. int u = str[i] - 'a'; //将字母转化为数字
  7. if(!son[p][u]) son[p][u] = ++idx;
  8. //该节点不存在,创建节点,其值为下一个节点位置
  9. p = son[p][u]; //使“p指针”指向下一个节点位置
  10. }
  11. cnt[p]++; //结束时的标记,也是记录以此节点结束的字符串个数
  12. }

查询操作:

  1. int query(char *str)
  2. {
  3. int p = 0;
  4. for(int i = 0; str[i]; i++)
  5. {
  6. int u = str[i] - 'a';
  7. if(!son[p][u]) return 0; //该节点不存在,即该字符串不存在
  8. p = son[p][u];
  9. }
  10. return cnt[p]; //返回字符串出现的次数
  11. }

本题完整代码:

  1. //一维是结点总数,而结点和结点之间的关系(谁是谁儿子)存在第二个维度
  2. //比如[0][1]=3, [0]表示根节点,[1]表示它有一个儿子‘b’,这个儿子的下标是3;接着如果有一个[3][2]=8 ;
  3. // 说明根节点的儿子‘b’也有一个儿子‘c’,这个孙子的下标就是8;
  4. //这样传递下去,就是一个字符串。随便给一个结点][x][y], 并不能看出它在第几层,只能知道,它的儿子是谁
  5. #include<bits/stdc++.h>
  6. using namespace std;
  7. #define rep(i,a,b) for(int i=(a);i<=(b);i++)
  8. #define lop(i,a,b) for(int i=(a);i<(b);i++)
  9. #define dwn(i,a,b) for(int i=(a);i>=(b);i--)
  10. #define el '\n'
  11. typedef pair<int,int> PII;
  12. using LL = long long;
  13. const int INF=0x3f3f3f3f;
  14. const int N=1e5+10;
  15. int son[N][26],cnt[N],idx;
  16. // 0号点既是根节点,又是空节点
  17. // son[][]存储树中每个节点的子节点
  18. // cnt[]存储以每个节点结尾的单词数量
  19. void insert(char str[])
  20. {
  21. int p=0;
  22. for(int i=0;str[i];i++)
  23. {
  24. int u=str[i]-'a';
  25. if(!son[p][u])son[p][u]=++idx;
  26. p=son[p][u];
  27. }
  28. cnt[p]++;
  29. }
  30. int query(char str[])
  31. {
  32. int p=0;
  33. for(int i=0;str[i];i++)
  34. {
  35. int u=str[i]-'a';
  36. if(!son[p][u])return 0;
  37. p=son[p][u];
  38. }
  39. return cnt[p];
  40. }
  41. void solve()
  42. {
  43. char op;
  44. char s[N];
  45. cin>>op>>s;
  46. if(op=='I')insert(s);
  47. else cout<<query(s)<<el;
  48. }
  49. int main()
  50. {
  51. ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  52. int t = 1;
  53. cin>>t;
  54. while(t--)
  55. solve();
  56. return 0;
  57. }

例题 (01字典树 求异或)acwingP143:https://www.acwing.com/problem/content/145/

思路:将每个数以二进制方式存入字典树,找的时候从最高位去找有无该位的异。如果有异,就往这走,反之走能走的路。

代码(附带详细注释)

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define rep(i,a,b) for(int i=(a);i<=(b);i++)
  4. #define lop(i,a,b) for(int i=(a);i<(b);i++)
  5. #define dwn(i,a,b) for(int i=(a);i>=(b);i--)
  6. #define el '\n'
  7. typedef pair<int,int> PII;
  8. using LL = long long;
  9. const int INF=0x3f3f3f3f;
  10. const int N=1e5+10;
  11. int son[N*31][2],idx;
  12. int n,a[N];
  13. void insert(int x)
  14. {
  15. int p=0;
  16. dwn(i,30,0)
  17. {
  18. int u=x>>i&1;//取x的第i位二进制数是什么
  19. if(!son[p][u])son[p][u]=++idx;
  20. p=son[p][u];
  21. }
  22. }
  23. int search(int x)
  24. {
  25. int p=0,res=0;
  26. dwn(i,30,0)//从最大位开始找
  27. {
  28. int u=x>>i&1;
  29. if(son[p][!u])//如果当前层有不同的数
  30. {
  31. p=son[p][!u];
  32. res=res*2+1;//*2相当于左移一位,如果找到对应位上有不同的数字,就再加一
  33. //感觉就是边转十进制边异或(不一样就+1)
  34. }
  35. else
  36. {
  37. p=son[p][u];
  38. res=res*2+0;//如果相同则*2即可
  39. }
  40. }
  41. return res;
  42. }
  43. void solve()
  44. {
  45. cin>>n;
  46. rep(i,1,n)
  47. {
  48. cin>>a[i];
  49. insert(a[i]);//插入
  50. }
  51. int ans=0;
  52. rep(i,1,n)
  53. ans=max(ans,search(a[i]));//找到最大异或值
  54. cout<<ans<<el;
  55. }
  56. int main()
  57. {
  58. ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  59. int t = 1;
  60. //cin>>t;
  61. while(t--)
  62. solve();
  63. return 0;
  64. }

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/727762
推荐阅读
  

闽ICP备14008679号