Trie字典树

文章目录

什么是 $T r i e$ 树
- 一般条件
AcWing 835. Trie字符串统计
- CODE
- - 解释一下 $in ser t ()$ 函数
  - $i d x$ 的意义

什么是 $T r i e$ 树

一种树结构，用来存储字符串，能够查询某字符串是否存在

Trie

由一个统一的根节点 $roo t$ 发散开，存储字符
- 如果下一个字符之前有用过，就顺着之前的路线往后走
- 如果下一个字符与之前的某串不重合，就另开一个路线继续走下去
最后如果串存完了在末尾打个标记
- 比如：之前存过字符串 $^{'} ab c d e f^{'}$ ，我们再存 $^{'} ab c^{'}$ 就会发现后者是前者的子串，如果不打标记就发现不了这个串

一般条件

一般题目中都会说明是全大写字母或者全小写字母，所以说数组开的范围不会太大，当然也有大范围。（我在写啥？？？《-_-》）

AcWing 835. Trie字符串统计

板子题：https://www.acwing.com/activity/content/problem/content/883/

CODE

#include <iostream>

using namespace std;

// 定义常量N为100010，这是我们预设的最大节点数量
const int N = 100010;

// son数组用于存储每个节点的子节点，每个节点有26个子节点，对应26个英文字母
// cnt数组用于存储每个节点结束的单词数量
// idx用于节点编号，每当我们创建一个新节点时，idx会加1
// str用于存储输入的字符串
int son[N][26], cnt[N], idx;
char str[N];

// 插入函数，用于将一个字符串插入到字典树中
void insert(char *str)
{
    // p是当前节点的编号，一开始我们在根节点，所以p=0
    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];		// 不能标记为idx，因为可能前面部分串有过记录，用idx就不对了
    }
    // 遍历完字符串后，我们在一个节点结束，所以该节点的单词数量加1
    cnt[p] ++ ;				// 这个也是同理，不能用idx
}

// 查询函数，用于查询一个字符串在字典树中出现的次数
int query(char *str)
{
    // p是当前节点的编号，一开始我们在根节点，所以p=0
    int p = 0;
    // 遍历输入字符串的每个字符
    for (int i = 0; str[i]; i ++ )
    {
        // 计算当前字符对应的编号
        int u = str[i] - 'a';
        // 如果当前节点没有对应的子节点，说明字符串不存在，返回0
        if (!son[p][u]) return 0;
        // 转移到子节点
        p = son[p][u];
    }
    // 返回当前节点的单词数量，即字符串在字典树中出现的次数
    return cnt[p];
}

// 主函数
int main()
{
    // n是操作数量
    int n;
    scanf("%d", &n);
    // 处理每个操作
    while (n -- )
    {
        // op是操作类型，str是操作的字符串
        char op[2];
        scanf("%s%s", op, str);
        // 如果操作类型是"I"，则插入字符串
        if (*op == 'I') insert(str);
        // 否则，查询字符串并打印出现次数
        else printf("%d\n", query(str));
    }

    return 0;
}

解释一下 $in ser t ()$ 函数

首先读入了待插入的字符串str
找到根节点 $roo t$ —> p = 0，也就是在son[0]位置是我们的根节点位置，由这个位置往后寻找
- 先读入下一个字符，然后在后面 $26$ 个字符空间中看这个字符是否被标记过
  - 如果被标记过则说明之前的某一字符串的这部分跟插入的串重合，拿着标记号去跟着之前的串走，也就是代码：
```
p = son[p][u];
```
  - 如果未标记则说明之前没有串跟它重合，则需要自己开一条线往后走，同时给这个字符赋予新的编号++idx，代表我走过这条路，索引号是idx，也就是代码：
```
if (!son[p][u]) son[p][u] = ++ idx;
```
最后串读完了，打个标记，就是字符串最后的字符拿到的编号为索引的数量数组cnt[p]++
对于 $q u ery ()$ 函数也是一样的思路