MENU

【简单】Trie字符串统计

• June 11, 2021 • Read: 254 • 数据结构与算法,学习笔记,算法&题库

维护一个字符串集合,支持两种操作:

  1. “I x”向集合中插入一个字符串 $x$;
  2. “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;
}

Archives QR Code
QR Code for this page
Tipping QR Code
Leave a Comment