912. Trie字符串统计
时间限制：1000 MS 内存限制：64 MB
题目描述
# Trie字符串统计 ## 题目描述 维护一个初始为空的字符串集合，支持以下两种操作： 1. `I x`：向集合中插入字符串 $x$。 2. `Q x`：查询字符串 $x$ 当前在集合中出现的次数。 同一个字符串可以被重复插入，每次插入都会使其出现次数增加 $1$。查询只统计与 $x$ 完全相同的字符串，不统计以 $x$ 为前缀的其他字符串。 共有 $N$ 个操作，所有输入字符串均只包含小写英文字母。 ## 输入格式 从文件 `trie.in` 中读入数据。 第一行包含一个整数 $N$，表示操作数。 接下来 $N$ 行，每行包含一个操作指令，格式为 `I x` 或 `Q x`，其中 $x$ 为字符串。 ## 输出格式 将结果输出到文件 `trie.out` 中。 对于每个查询操作 `Q x`，输出一个整数，表示字符串 $x$ 当前在集合中出现的次数。 每个结果占一行。 ## 数据范围 - $1 \le N \le 2 \times 10^4$。 - 所有输入字符串的总长度不超过 $10^5$。 - 字符串仅包含小写英文字母。 ## 样例输入 ``` 5 I abc Q abc Q ab I ab Q ab ``` ## 样例输出 ``` 1 0 1 ``` ## 样例说明 插入 `abc` 后，查询 `abc` 的结果为 $1$。此时 `ab` 尚未被插入，虽然它是 `abc` 的前缀，但查询结果仍为 $0$。 插入 `ab` 后，再次查询 `ab`，结果为 $1$。 ## 时间与空间限制 - 时间限制：$1000$ 毫秒。 - 内存限制：$64$ MB。