AcWing
  • 首页
  • 题库
  • 题解
  • 分享
  • 问答
  • 活动
  • 应用
  • 吐槽
  • 登录/注册

Trie树:DAY5-1

作者: 作者的头像   cht ,  2020-05-21 17:58:11 ,  阅读 265


11


1

Trie树

Trie树是一种可以高效的存储和查找字符串的数据结构。
先科普一下。
Trie树又叫前缀树
Trie树不光可以存储字符串,还可以存储数字甚至汉字!
* Trie树查找的时间复杂度近乎O(1)!

那我们的Trie树是如何存储或查找的呢?
其实Trie很简单。

Trie是一种非常简单的数据结构——yxc巨巨巨巨巨佬

那Trie树到底是如何用近乎O(1)这么NB的时间复杂度来去存储我们的字符串呢?

首先我们可以想像出一颗树,注意不一定是二叉树(二叉树就是每个父节点均有两个子节点。)
然后随便写一个单词(这里我写yxcnb),那我们把这个树进行如下操作:
具体请看视频。
在ACSABER的交流群中的文件里:
批注 2020-05-21 173613.png
也可以打开美篇链接查看~
Trie树讲解~
不香看视频的同学这里我讲解一下。
每次我们插入一个字符串时先判断有没有对应字符串当前字符的节点。
如果有,我们走过去,否则我们新创建一个节点然后走过去。
这就是y总说的:

不管这个字符有没有路,它都走过去了,没有路会自己铺一条——yxc

那我们怎么查找呢?
我们可以每次判断与当前字符对应节点是否存在,如果不存在说明没有这个字符串,存在就继续走下去。
当然这一波下来还是很抽象,建议大家看看视频~
然后我们回来看看具体咋写。

首先我们定义一下需要用的数组~

int son[100010][26];/*所有的Trie题都会给定范围,默认范围是所有英文小写字母。*/
int idx;//当前用到的点。
char str[100010];//整个的字符串。

然后是插入操作。

void add(char *str)
{
    int p = 0;//存储遍历到了什么店。
    for(int i = 0; str[i]; i ++)//这里从前向后便利str字符串,最后\0会自动停止。
    {
        int u = str[i] - 'a';//算出当前值映射成数字后的数,减去偏移量a
        if(!son[p][u]) son[p][u] = ++ idx;//没有路也要自己铺路。
        p = son[p][u];//如果没有路已经铺好了路,走下去到下一个节点。
    }
}

查找操作~

这里我们定义一个s数组查找。(通过字符串找到对应s数组中的值)

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 s[p];//最后返回对应s数组中的值
}

接下来一道题:Trie字符串统计

好我们先来读下题。
我们有两种操作分别为插入和查找,我们就能用Trie实现。
因为上面已经呈现过代码了所以直接上完整的AC代码:

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int N = 100010;
int n, son[N][26], cnt[N], idx;
char str[N];
void add(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()
{
    cin >> n;
    while(n --)
    {
        char op[2];
        scanf("%s%s", op, str);
        if(*op == 'I')
        {
            add(str);//插入操作就把字符串插进去
        }
        else cout<< query(str) << endl;//查找操作我们就返回查找
    }
    return 0;
}

今天的作业:最大抑或对

好了今天分享就到这里了

未经允许,请勿抄袭!

希望大家顶我,让我拥有更大的动力!

这是我的全部分享

bye~

12 评论


用户头像
Protein   7个月前     回复

这世上本没有路,走的人多了,就成了路——鲁迅
这世上本没有数据结构,搞事情的人多了便有了数据结构——Protein

用户头像
cht   7个月前     回复

哈哈哈哈哈哈


用户头像
垫底抽风   8个月前     回复

哎这个作业好像忘交了,来交一下~

#include <iostream>
#include <utility>

const int N = 100010;

struct trie {
    int trie[N * 32][2];
    int idx = 0;
    void insert(int x) {
        for (int i = 30, p = 0; ~i; i -- ) {
            int u = x >> i & 1;
            if (!trie[p][u]) trie[p][u] = ++ idx;
            p = trie[p][u];
        }
    }
    int query(int x) {
        int ans = 0;
        for (int i = 30, p = 0; ~i; i -- ) {
            int u = x >> i & 1;
            if (trie[p][!u]) {
                ans |= 1 << i;
                p = trie[p][!u];
            } else {
                p = trie[p][u];
            }
        }
        return ans;
    }
};

inline int max(int a, int b) {
    return a > b ? a : b;
}

int main() {
    int n, res = 0;
    trie trie;
    for (scanf("%d", &n); n -- ;) {
        int x;
        scanf("%d", &x);
        trie.insert(x);
        res = max(res, trie.query(x));
    }
    printf("%d", res);
    return 0;
}

用户头像
垫底抽风   8个月前     回复

确定是O(1)嘛。。亦或对里面的trie不难算出是1log吧。。字符串的需要时间就更长了啊。。

用户头像
cht   8个月前     回复

对h,所以是近乎O(1),注意近乎

用户头像
cht   8个月前     回复

对啊,只是近乎

用户头像
垫底抽风   8个月前    回复了 cht 的评论     回复

这一点都不近乎吧。。


用户头像
silver.bullet   8个月前     回复

没声音[doge]


用户头像
silver.bullet   8个月前     回复

登QQ要验证。。。。

用户头像
cht   8个月前     回复

可以看美篇~


用户头像
silver.bullet   8个月前     回复

顶了 感谢分享

用户头像
cht   8个月前     回复

hh,建议看看视频~

你确定删除吗?

© 2018-2021 AcWing 版权所有  |  京ICP备17053197号-1
联系我们  |  常见问题
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标
请输入绑定的邮箱地址
请输入注册信息