TRIE(2)

实现TRIE结构

第一种方法是用一个二维数组来存储:

int trie[MAX_NODE][CHARSET];
int k;

 其中MAX_NODE是trie中最大能存储的节点数目,CHARSET是字符集的大小,k是当前trie中包含有多少个节点。Triei的值是0表示trie树中i号节点,并没有一条连出去的边,满足边上的字符标识是字符集中第j个字符(从0开始);triei的值是正整数x表示trie树中i号节点,有一条连出去的边,满足边上的字符标识是字符集中第j个字符,并且这条边的终点是x号节点  举个例子,下图中左边是trie树,右边是二维数组trie中非0的值

 用二维数组实现trie的好处是用起来非常方便,因为trie的insert和search操作都要经常判断一个节点有没有标识某个字符的边,以及边的终点是几号节点。用二维数组的话,我们只要看相应的triei的值即可。用二维数组的缺点是可能会浪费很多空间,因为我们对每一个节点都用了一个字符集大小的数组存储子节点号,但实际上每个点连出去的边很稀疏。比如上图中实际上每个点只有0-2个子节点,但是我们给每个节点都开辟了一个大小是26的数组去存储子节点 第二种方法是像邻接表一样用vector来存储每个节点的子节点:

vector<pair<char, int> > trie[MAX_NODE];
int k;

 我们把i号节点的子节点和边的信息存在trie[i]里。每一个pair<char, int>其实是(边的标识,子节点号)这样的二元组:

 用vector的好处是可以节省很多空间,起码理论上空间复杂度是O(N)的,其中N是节点总数。缺点是每次我们想找i号节点有没有标识是某个字符ch的边时,都需要遍历一遍trie[i]这个vector,而不能像数组一样直接查找 第三种方法是用unordered_map

unordered_map<char, int> trie[MAX_NODE];
int k;

 使用unordered_map看上去是一个两全其美的做法。每次我们想找i号节点有没有标识是某个字符ch的边时,只要看triei的值即可。同时理论上也不需要每个节点都占用CHARSERT大小的空间去存储子节点,而是有几个子节点就用到几个子节点的空间。理论上时空复杂度都是O(N)  我们采用数组的方式来存储,下面分别看一下insert和search方法

#include <iostream>
#include <cstring>
using namespace std;
const int MAX_NODE = 1000000 + 10;
const int CHARSET = 26;
int trie[MAX_NODE][CHARSET] = {0};
int color[MAX_NODE0] = {0};
int k = 1;
void insert(char *w) {
    int len = strlen(w);
    int p = 0;
    for(int i = 0;i < len;i++) {
        int c = w[i] - 'a';
        if(!trie[p][c]) {
            trie[p][c] = k;
            k++;
        }
        p = trie[p][c];
    }
    color[p] = 1;
}

 代码的第6~8行,一开始trie[][]被初始化为0,保证每个节点被创建出来时,都没有子节点。K初始化为1表示一开始只有1个节点,也就是0号节点根节点。Color是用来标记一个节点是不是终结点。Color[i]=1标识i号节点是终结点  第9~21行是插入函数insert(w),w是字符指针,实际上可以看作是一个字符串  第11行是p从0号节点开始。第12~19行是依次插入w的每一个字符。第13行是计算w[i]是字符集第几个字符,这里我们假设字符集只包含26个小写字母。第14~17行是如果p没有连出标识是w[i]的边,那么就创建一个。这里新创建的节点一定就是k号节点。所谓创建新节点实际上也没什么可创建的,新节点就是个编号。所以我们直接令triei=k即可,然后将k累加1,整个创建过程就完成了。第18行是沿着标记着w[i]的边移动到下一个节点。最后第20行,是将最后到达的节点p标记为终结点  有了插入,我们再看查找代码如何实现:

int search(char *s) {
    int len = strlen(s);
    int p = 0;
    for(int i = 0;i < len;i++) {
        int c = s[i] - 'a';
        if(!trie[p][c]) return 0;
        p = trie[p][c];
    }
    return color[p] == 1;
}

 查找的代码就比较简单直观,search返回0表示trie中没有s,返回1表示有s。第3行是从p=0也就是根节点开始。第4~8行是枚举s的每一个字符。第5行是计算当前字符s[i]在字符集的序号。第6行是判断p节点有没有连出标识s[i]字符的边,如果没有,说明现在无路可走,直接返回0;如果有的话,第7行就是移动到下一个节点。如果整个循环结束还没有return 0,那就说明成功沿着s的每一个字符到达了p节点。这时只要判断p节点是不是终结点即可,也就是第9行的代码

例1 题目链接:hihoCoder1014

 这道题目的大意是给定一个包含N个字符串的集合,然后再给出M个询问。每次询问给出一个字符串s,要求你回答集合中有几个字符串的前缀是s  比如集合是{ babaab, babbbaaaa, abba, aaaaabaa, babaabab}询问前缀是bab,答案就是3。因为有babaab, babbbaaaa, babaabab 三个字符串前缀是bab  这道题是一道很经典的用Trie解决的题目。首先我们把集合中的N个字符串都插入到trie中。对于每一个查询s我们在trie中查找s,如果查找过程中无路可走,那么一定没有以s为前缀的字符串。如果最后停在一个节点p,那我们就要看看以p为根的子树里一共有多少终结点。终结点的数目就是答案

 比如在上图中,询问是s=”in”。我们会停在2号节点上。这棵子树一共有3个终结点,对应着3个字符串”in”, “inn”, “int”,这三个字符串前缀都是”in”,所以答案是3  但是如果我们每次都遍历以P为根的子树,那时间复杂度就太高了。解决的办法是用空间换时间,我们增加一个数组int cnt[MAX_NODE],cnt[i]记录的是以i号节点为根的子树中,有几个终结点。然后我们每次insert一个字符串的时候,顺便就把沿途的节点的cnt值都+1。这样就不用每次遍历以P为根的子树,而是直接输出cnt[P]即可

#include <iostream>
#include <cstring>
using namespace std;
const int MAX_NODE = 1000000 + 10;
const int CHARSET = 26;
int trie[MAX_NODE][CHARSET] = {0};
int cnt[MAX_NODE] = {0};
int n,m,k = 1;
char s[20];
void insert(char *w) {
    int len = strlen(w);
    int p = 0;
    for(int i = 0;i < len;i++) {
        int c = w[i] - 'a';
        if(!trie[p][c]) {
            trie[p][c] = k;
            k++;
        }
        p = trie[p][c];
        cnt[p]++;
    }
}
int search(char *s) {
    int len = strlen(s);
    int p = 0;
    for(int i = 0;i < len;i++) {
        int c = s[i] - 'a';
        if(!trie[p][c]) return 0;
        p = trie[p][c];
    }
    return cnt[p];
}
int main() {
    memset(trie,0,sizeof(trie));
    scanf("%d",&n);
    for(int i = 0;i < n;i++) {
        scanf("%s",s);
        insert(s);
    }
    scanf("%d",&m);
    while(m--) {
        scanf("%s",s);
        int ans = search(s);
        printf("%d\n",ans);
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏我的技术专栏

C++ 顺序容器基础知识总结

2105
来自专栏我是攻城师

Apache Pig学习笔记(二)

3589
来自专栏C语言及其他语言

【编程经验】C语言逆向之表达式短路分析及应用

关注我们 大家在学习C语言过程中,可能会见到过一些这样的题,就是表达式短路,表达式短路主要体现在C语言中逻辑运算符&&和||。今天将对表达式短路...

3237
来自专栏数据结构与算法

agc016D - XOR Replace(图论 智商)

不难看出,我们把所有数$xor$起来的数替换掉之后再次$xor$,得到的一定是被替换掉的数。

915
来自专栏数据结构与算法

27:除以13

27:除以13 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 输入一个大于0的大整数N,长度不超过100位,要求输出其除...

3139
来自专栏ACM算法日常

UVA11988:悲剧文本(模拟链表)

You’re typing a long text with a broken keyboard. Well it’s not so badly broken....

871
来自专栏数据结构与算法

洛谷P3812 【模板】线性基

1 \leq n \leq 50, 0 \leq S_i \leq 2 ^ {50}1≤n≤50,0≤Si​≤250

682
来自专栏debugeeker的专栏

《coredump问题原理探究》Linux x86版7.7节 set对象

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/xuzhina/article/detai...

1001
来自专栏偏前端工程师的驿站

PLT:说说Evaluation strategy

Brief                                 在学习方法/函数时,我们总会接触到 按值传值 和 引用传值 两个概念。像C#是按值传...

2106
来自专栏人工智能LeadAI

共享变量 tensorflow解读

你可以在怎么使用变量中所描述的方式来创建,初始化,保存及加载单一的变量.但是当创建复杂的模块时,通常你需要共享大量变量集并且如果你还想在同一个地方初始化这所有的...

1212

扫码关注云+社区

领取腾讯云代金券