【第十三课】Trie字符串统计(acwing-835 / 二维数组的含义 / c++代码)

2023-12-29 19:30:51

思想

Trie树在我们之前学习树的时候简单提过一嘴。

Trie树也称为前缀树或字典树,是一种用于高效存储和查找字符串的数据结构。Trie树的主要思想是利用字符串之间的公共前缀来节省存储空间,提高查询效率。

节点表示:Trie树中的每个节点代表一个字符串,这个字符串是由根节点到该节点的路径上的字符组成的。

公共前缀:如果两个字符串有公共的前缀,那么它们在Trie树中的路径会有公共的部分。这样可以避免存储重复的前缀,从而节省空间。

边表示字符:Trie树中的每条边都对应一个字符从一个节点到其子节点的边对应的字符就是 子节点对应的字符串 相对于 父节点对应的字符串 多出的那个字符

就像图片中这样

代码如下?

#include<iostream>
using namespace std;
const int N=1e5+10;
int son[N][26],count[N],idx;
//son是一个二维数组,行表示一个节点,列表示该节点的子节点,最大为26个字母都为其子节点
//count数组记录以特定编号节点所对字符结尾的字符串个数,数组元素个数取决于trie树的节点个数
//idx给每个插入进来的节点分配编号
int n;
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;//因为根节点是0,其余节点从1开始编号
        p=son[p][u];//每次查找的末尾的节点
    }
    count[p]++;//以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 count[p];
}
int main()
{
    cin>>n;
    while(n--)
    {
        char order[2];
        scanf("%s",&order);
        scanf("%s",&str);
        if(order[0]=='I')
        {
            Insert(str);
        }
        else if(order[0]=='Q')
        {
            printf("%d\n",query(str));
        }
    }
    return 0;
}

一些解释

count数组?

每个字符串的末尾会做出标记,我们这里的标记方式就是用count数组的计数实现。如果我们多次插入相同的字符串,count数组就会统计多次,应用为:统计文本中每个单词的出现次数,或者在搜索引擎中统计每个查询的频率

二维数组-son

这里我们创建了二维数组son,son数组实际意义是表示的是两个节点之间的边,其行元素表示树中的节点,列元素表示该节点的子节点。其存储的内容是该节点对应的编号,我们每次通过

int u = str[i] - 'a';

这段代码的ASCII码转换,对应出相应边上的字符。

感觉主要是这个二维数组不太好理解,,,注意其表示的含义即可。

我刚开始想不出来比较疑惑的是二维数组与我们实际trie树的关系,bing给出了解答


如果有问题欢迎指出,非常感谢!!

也欢迎交流和建议哦!

文章来源:https://blog.csdn.net/Swillow_/article/details/135283239
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。