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

思想

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给出了解答

---

如果有问题欢迎指出，非常感谢！！

也欢迎交流和建议哦！