← 返回题目列表

Codeforces · 1207/G

G. 独立专辑

中文机器翻译题面 查看原题

Mishka 最喜欢的实验独立乐队最近发布了一张新专辑!那张专辑的歌曲有一个共同点。每个名称 $$$s_i$$$ 是以下类型之一:

- $$$1~c$$$ — 单个小写拉丁字母;
- $$$2~j~c$$$ — 名称 $$$s_j$$$ ($$$1 \le j < i$$$) 末尾附加一个小写拉丁字母。

歌曲编号从 $$$1$$$ 到 $$$n$$$。保证第一首歌曲的类型始终为 $$$1$$$。

Vova对新专辑相当感兴趣,但他确实没有时间完整地听它。因此,他向米什卡询问了一些问题,以确定某首歌是否值得听。问题具有以下格式:

- $$$i~t$$$ — 统计字符串 $$$t$$$ 在 $$$s_i$$$(专辑第 $$$i$$$ 歌曲的名称)中出现的次数,作为连续子字符串,$$$t$$$ 仅由小写拉丁字母组成。

Mishka 并没有质疑该信息的目的,但他很难提供它。你能帮 Mishka 回答 Vova 的所有问题吗?

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 4 \cdot 10^5$$$) — 专辑中的歌曲数。

接下来的 $$$n$$$ 行包含专辑中第 $$$i$$$ 歌曲的描述,格式如下:

- $$$1~c$$$ — $$$s_i$$$ 是单个小写拉丁字母;
- $$$2~j~c$$$ — $$$s_i$$$ 是名称 $$$s_j$$$ ($$$1 \le j < i$$$),末尾附加一个小写拉丁字母。

下一行包含一个整数 $$$m$$$ ($$$1 \le m \le 4 \cdot 10^5$$$) — Vova 的问题数。

接下来的 $$$m$$$ 行包含第 $$$j$$$ 个 Vova 问题的描述,格式如下:

- $$$i~t$$$ ($$$1 \le i \le n$$$, $$$1 \le |t| \le 4 \cdot 10^5$$$) — 将 $$$s_i$$$(专辑中第 $$$i$$$ 歌曲的名称)中字符串 $$$t$$$ 的出现次数作为连续子字符串进行计数, $$$t$$$ 仅由小写拉丁字母组成。

保证问题字符串$$$t$$$的总长度不超过$$$4 \cdot 10^5$$$。

输出

对于每个问题,打印一个整数 - 问题字符串 $$$t$$$ 在专辑第 $$$i$$$ 歌曲的名称中作为连续子字符串出现的次数。

示例

输入 #1

20
1 d
2 1 a
2 2 d
2 3 a
2 4 d
2 5 a
2 6 d
2 7 a
1 d
2 9 o
2 10 k
2 11 i
2 12 d
2 13 o
2 14 k
2 15 i
2 1 o
2 17 k
2 18 i
2 15 i
12
8 da
8 dada
8 ada
6 dada
3 dada
19 doki
19 ok
16 doki
15 doki
9 d
1 a
20 doki

输出 #1

4
3
3
2
0
1
1
2
1
1
0
2

注意

第一个示例的歌曲名称:

1.d
2. 达
3.爸爸
4.达达
5.爸爸
6.达达达
7. 爸爸
8.达达达
9.d
10. 做
11. 多克
12. doki
13. dokid
14. dokido
15. dokidok
16. dokidoki
17. 做
18. 多克
19. doki
20. dokidoki

因此每个问题字符串的出现次数是:

1. 字符串“da”从名称“dadadada”中的位置 $$$[1, 3, 5, 7]$$$ 开始;
2. 字符串“dada”从名称“dadadada”中的位置 $$$[1, 3, 5]$$$ 开始;
3. 字符串“ada”从名称“dadadada”中的位置 $$$[2, 4, 6]$$$ 开始;
4. 字符串“dada”从名称“dadada”中的位置 $$$[1, 3]$$$ 开始;
5. 名字“dad”中没有出现字符串“dada”;
6. 字符串“doki”从名称“doki”中的位置$$$[1]$$$开始;
7. 字符串“ok”从名称“doki”中的位置$$$[2]$$$开始;
8. 字符串“doki”从名称“dokidoki”中的位置 $$$[1, 5]$$$ 开始;
9. 字符串“doki”从名称“dokidok”中的位置 $$$[1]$$$ 开始;
10. 字符串“d”从名称“d”中的位置 $$$[1]$$$ 开始;
11. 名称“d”中没有出现字符串“a”;
12. 字符串“doki”从名称“dokidoki”中的位置 $$$[1, 5]$$$ 开始。