题目描述

题目大意&链接

给定一个字符串集合，需要支持两种操作（需要高效存储和查找字符串，否则会超时）：

插入字符串（操作符为 I）
查询某个字符串出现的次数（操作符为 Q）

输入输出样例：
输入：

5
I abc
Q abc
Q ab
I ab
Q ab

输出：

1
0
1

详情：ac_835Trie字典树

解题思路

本题使用Trie 树（字典树）来高效处理字符串的插入和查询操作。Trie 树的核心思想是利用字符串的公共前缀来减少查询时间，从而达到插入和查询的时间复杂度均为 O (m)（m 为字符串长度）。

数据结构设计：可以看下面代码注释

// Trie（字典树）: 高效存储和查找字符串集合的数据结构
const int N = 100010;

int son[N][26]; //存储从节点 P 沿着 i 这条边走到的子节点
int cnt[N]; //存储以节点 p 结尾的单词插入次数
int idx;    //给每个节点编号（节点数）
char str[N];    //处理的字符串

插入操作：从根节点开始，遍历字符串的每个字符；将字符转换为对应的索引（0~25）；如果当前节点没有对应子节点，创建新节点；遍历结束后，在最后一个节点的 cnt 上加 1，表示该字符串出现次数 + 1。

void insert(char* str)
{
    int p = 0; // 从根节点（编号0）开始
    for (int i = 0; str[i]; i++)
    {
        int u = str[i] - 'a';  // 将字符映射为0-25的索引
        if (!son[p][u]) son[p][u] = ++idx; // 如果路径不存在，创建新节点
        p = son[p][u]; // 移动到下一个节点
    }
    cnt[p]++; // 标记字符串结尾，计数器加1
}

查询操作：从根节点开始遍历字符串；如果中途路径不存在，说明字符串不在集合中，返回 0 ；遍历结束后，返回最后一个节点的 cnt 值，表示该字符串出现的次数。

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; // 路径不存在，返回0
        p = son[p][u]; // 移动到下一个节点
    }
    return cnt[p]; // 返回该节点的计数器值
}

如果大家还是觉得上面的题解比较难懂，不妨看看这个视频：Trie字典树

完整代码

#define  _CRT_SECURE_NO_WARNINGS
#include <iostream>

using namespace std;
// Trie（字典树）: 高效存储和查找字符串集合的数据结构
const int N = 100010;

int son[N][26]; //存储从节点 P 沿着 i 这条边走到的子节点
int cnt[N]; //存储以节点 p 结尾的单词插入次数
int idx;    //给每个节点编号（节点数）
char str[N];    //处理的字符串

void insert(char* str)
{
    int p = 0; // 从根节点（编号0）开始
    for (int i = 0; str[i]; i++)
    {
        int u = str[i] - 'a';  // 将字符映射为0-25的索引
        if (!son[p][u]) son[p][u] = ++idx; // 如果路径不存在，创建新节点
        p = son[p][u]; // 移动到下一个节点
    }
    cnt[p]++; // 标记字符串结尾，计数器加1
}

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; // 路径不存在，返回0
        p = son[p][u]; // 移动到下一个节点
    }
    return cnt[p]; // 返回该节点的计数器值
}

int main()
{
    int n;
    scanf("%d", &n);
    while (n--)
    {
        char op[2];
        scanf("%s %s", op, str);
        if (*op == 'I') insert(str);
        else printf("%d\n", query(str));
    }

    return 0;
}

时间和空间复杂度

时间复杂度：O(m)，其中 m 为字符串长度
空间复杂度：O (N * 26)，N 为节点总数