Trie字符串统计

维护一个字符串集合，支持两种操作：

“I x”向集合中插入一个字符串 $x$；
“Q x”询问一个字符串在集合中出现了多少次。

共有 $N$ 个操作，输入的字符串总长度不超过 $\rm{10^5}$，字符串仅包含小写英文字母。

输入格式

第一行包含整数 $N$，表示操作数。
接下来 $N$ 行，每行包含一个操作指令，指令为“I x”和“Q x”中的一种。

输出格式

对于每个操作指令“Q x”，都要输出一个整数作为结果，表示 $x$ 在集合中出现的次数。
每个结果占一行。

数据范围

$\rm{1} \le N \le 2*{10^4}$

输入样例

5
I abc
Q abc
Q ab
I ab
Q ab

输出样例

1
0
1

题解

（Trie 树） 数据结构
插入操作：
从根节点开始，枚举当前字符串，如果对应字母节点存在，则进入下一个节点，否则创建节点。字符串枚举完成后，创建当前节点单词结尾标记。
查询操作：
同插入操作，如果任意一个字母节点不存在，则意味着该字符串一定不存在，否则继续枚举，最终范围尾节点的单词结尾标记。

C++ 代码

#include <iostream>

using namespace std;

const int N = 100010;

int son[N][26];//子节点最多26个（26个英文字母）
int cnt[N], idx;//下标为0的点即是根节点，又是空节点，cnt为以当前点结尾的单词数量，idx表示当前可用的节点
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;
        p = son[p][u];//进入下一个点，即子节点
    }
    cnt[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 cnt[p];//返回单词结尾标记，即以该节点结尾的单词数量
}
int main()
{
    int n;
    cin >> n;
    while(n--)
    {
        char op[2];
        scanf("%s%s", op, str);
        if(op[0] == 'I')
            insert(str);
        else
            cout << query(str) << endl;
    }
    return 0;
}

版权属于：字节星球/肥柴之家 （转载请联系作者授权）
原文链接：https://www.bytecho.net/archives/1812.html
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。

Catalog