← 返回题单
题单练习 提高组模版题
← 上一题 下一题 →

A7327 | 字典树模板

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

小明有一个单词仓库，仓库中一开始没有任何单词。

接下来会进行 $Q$ 次操作，每次操作有以下三种类型：

  • 1 s：向仓库中插入一个单词 $s$；
  • 2 s：查询单词 $s$ 在仓库中完整出现了多少次；
  • 3 s：查询仓库中有多少个单词以 $s$ 作为前缀。
注意，同一个单词可以被插入多次，每次插入都要计入答案。

你需要对每个查询操作输出答案。

输入格式

第一行输入一个整数 $Q$，表示操作次数。

接下来 $Q$ 行，每行输入一个整数 $op$ 和一个字符串 $s$，表示一次操作。

其中：

  • 当 $op=1$ 时，表示插入字符串 $s$；
  • 当 $op=2$ 时，表示查询字符串 $s$ 完整出现了多少次；
  • 当 $op=3$ 时，表示查询有多少个字符串以 $s$ 为前缀。

输出格式

对于每个 $op=2$ 或 $op=3$ 的操作，输出一行一个整数，表示查询结果。

输入输出样例

输入 #1
10
1 apple
1 app
1 apple
3 app
2 apple
2 app
2 appl
1 banana
3 ba
3 a
输出 #1
3
2
1
0
1
3
C++ 编辑器
输入
输出