AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

Trie树模板

作者: 作者的头像   wuog ,  2019-07-31 09:15:00 ,  所有人可见 ,  阅读 2872


9


4

Trie树

高效的存储和查找字符串集合的数据结构;

理解

从根节点开始,判断有没有该类字符,有就向下,没有就添加叶节点,依次存储,把所有结尾点标记一下,然后用Trie高速查找某一个字符出现的次数。
qwerwer
qwe
qerer
ertq
yuyu
先是依次存储qwerwer,然会第二段有qwe就不用添加新的叶节点,第三段因为e不相同,所以要添加一个叶节点用于存储erer,此后的基本类似,有就存储没有就添加;

相关模板

// 插入一个字符串
    void insert(char str[])
    {
        int p = 0;
        for (int i = 0; str[i]; i ++ )
        {
            int u = str[i] - 'a';
            //映射编号:0-25
            if (!son[p][u]) son[p][u] = ++ idx;
            //如果没有就创建一个
            p = son[p][u];
            //有就下一个点

        }
        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;
            //如果不存在某一个子节点,直接返回0;
            p = son[p][u];
            //有就进行下一个
        }
        return cnt[p];
    }   

模板例子

 [原题链接](https://www.acwing.com/problem/content/837/) 
 #include <iostream>

using namespace std;

const int N = 100010;

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];
    }
    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 n;
    scanf("%d", &n);
    while (n -- )
    {
        char op[2];
         cin>>op>>str;
        if (op[0] == 'I') insert(str);
        else cout<<query(str)<<endl;
    }
    return 0;
}

4 评论


用户头像
EOF_54845   2024-03-16 14:41      1    踩      回复

感谢分享!


用户头像
Conan15   2022-01-19 19:15         踩      回复

%%%我正在学这个东西哦,学到很多,谢谢大佬!


用户头像
jianzihao   2019-12-24 18:48         踩      回复

好

用户头像
wuog   2019-12-24 19:44         踩      回复

没有 hhhh


App 内打开
你确定删除吗?
1024
x

© 2018-2025 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息