• 数据结构--字典树(trie)


    概念:

    Trie 是一种能够快速插入和查询字符串的多叉树结构。、

    节点的编号各不相同,根节点编号为0,其他节点用来标识路径,还可以标记单词的插入次数,边表示字符。

    tire 维护字符串的集合,支持两种操作:

    1. 向集合中插入一个字符串

    2. 在集合中查询一个字符串

    建字典树

    儿子数组 son[p][26] : 存储从节点p沿着j这条边走到的子节点。边为26个小写字母(a~z)对应的映射值0~25,每个节点最多可以有26个分叉。

    计数数组 cnt[p] : 存储以节点p结尾的单词的插入次数

    节点编号 idx : 用来给节点编号

    1. 空 trie 仅有一个根节点,编号为0

    2. 从根开始插,枚举字符串的每个字符

         如果有儿子,则p指针走到儿子

         如果没有儿子,则 先创建儿子,p指针再走到儿子

    3. 在单词结束点记录插入次数

    模板:

    1. int son[N][26], cnt[N], idx;
    2. // 0号点既是根节点,又是空节点
    3. // son[][]存储树中每个节点的子节点
    4. // cnt[]存储以每个节点结尾的单词数量
    5. // 插入一个字符串
    6. void insert(char *str)
    7. {
    8. int p = 0;
    9. for (int i = 0; str[i]; i ++ )
    10. {
    11. int u = str[i] - 'a';
    12. if (!son[p][u]) son[p][u] = ++ idx;
    13. p = son[p][u];
    14. }
    15. cnt[p] ++ ;
    16. }
    17. // 查询字符串出现的次数
    18. int query(char *str)
    19. {
    20. int p = 0;
    21. for (int i = 0; str[i]; i ++ )
    22. {
    23. int u = str[i] - 'a';
    24. if (!son[p][u]) return 0;
    25. p = son[p][u];
    26. }
    27. return cnt[p];
    28. }

    例题:(835. Trie字符串统计 - AcWing题库

    题目:

    维护一个字符串集合,支持两种操作:

    1. I x 向集合中插入一个字符串 x;
    2. Q x 询问一个字符串在集合中出现了多少次。

    共有 N 个操作,所有输入的字符串总长度不超过 105105,字符串仅包含小写英文字母。

    输入格式

    第一行包含整数 N,表示操作数。

    接下来 N 行,每行包含一个操作指令,指令为 I x 或 Q x 中的一种。

    输出格式

    对于每个询问指令 Q x,都要输出一个整数作为结果,表示 x 在集合中出现的次数。

    每个结果占一行。

    数据范围
    1≤N≤2∗10^4
    输入样例:
    1. 5
    2. I abc
    3. Q abc
    4. Q ab
    5. I ab
    6. Q ab
    输出样例:
    1. 1
    2. 0
    3. 1

    代码:

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. #include
    9. #include
    10. #include
    11. const int N = 1e5 + 10;
    12. using namespace std;
    13. typedef pair<int ,int> PII;
    14. int son[N][26],cnt[N],idx;
    15. char str[N];
    16. void insert(char str[]){
    17. int p = 0;
    18. for(int i = 0;str[i];i ++){
    19. int u = str[i] - 'a';
    20. if(!son[p][u])
    21. son[p][u] = ++idx;
    22. p = son[p][u];
    23. }
    24. cnt[p] ++;
    25. }
    26. int query(char str[]){
    27. int p = 0;
    28. for(int i = 0;str[i];i ++){
    29. int u = str[i] - 'a';
    30. if(!son[p][u]) return 0;
    31. p = son[p][u];
    32. }
    33. return cnt[p];
    34. }
    35. int main(){
    36. int n;
    37. cin >> n;
    38. while(n --){
    39. char op[2];
    40. scanf("%s%s",op,str);
    41. if(op[0] == 'I')
    42. insert(str);
    43. else printf("%d\n",query(str));
    44. }
    45. return 0;
    46. }

  • 相关阅读:
    90、一维装箱
    DOM中的diff算法详解
    微信小程序post请求数据传送不出去
    java毕业设计鑫通物流车辆调度系统mp4Mybatis+系统+数据库+调试部署
    2022年湖北工业大学招生简章之高起专、专升本非全日制学历提升
    Tilemap瓦片资源
    R语言ggplot2可视化:使用ggpubr包的ggdensity函数可视化密度图、使用fill参数自定义密度图的填充色
    3ds max 2020 vray 5.0 渲染设置
    STM32智能物流机器人系统教程
    机器学习VS深度学习
  • 原文地址:https://blog.csdn.net/weixin_72982195/article/details/132586378