CF1207G Indie Album

Mishka 最喜欢的实验独立乐队最近发布了一张新专辑！这张专辑中的歌曲名有一个共同的特点。每个名字 $s_i$ 都属于以下两种类型之一： - $1~c$ —— 一个小写拉丁字母； - $2~j~c$ —— 将第 $j$ 首歌的名字 $s_j$（$1 \le j < i$）末尾添加一个小写拉丁字母得到。 歌曲编号从 $1$ 到 $n$。保证第一首歌一定是类型 $1$。 Vova 对新专辑很感兴趣，但他实在没有时间全部听完。因此他向 Mishka 提出了一些问题，以判断某首歌是否值得一听。问题的格式如下： - $i~t$ —— 统计字符串 $t$ 在第 $i$ 首歌的名字 $s_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$ 是将第 $j$ 首歌的名字 $s_j$ 末尾添加一个小写拉丁字母得到（$1 \le j < i$）。 接下来一行包含一个整数 $m$（$1 \le m \le 4 \cdot 10^5$），表示 Vova 的问题数量。 接下来的 $m$ 行，每行描述第 $j$ 个问题，格式如下： - $i~t$（$1 \le i \le n$，$1 \le |t| \le 4 \cdot 10^5$）—— 统计字符串 $t$ 在第 $i$ 首歌的名字 $s_i$ 中作为连续子串出现的次数，$t$ 只包含小写拉丁字母。 保证所有问题字符串 $t$ 的总长度不超过 $4 \cdot 10^5$。

对于每个问题，输出一个整数，表示问题字符串 $t$ 在第 $i$ 首歌的名字 $s_i$ 中作为连续子串出现的次数。

第一个样例的歌曲名如下： 1. d 2. da 3. dad 4. dada 5. dadad 6. dadada 7. dadadad 8. dadadada 9. d 10. do 11. dok 12. doki 13. dokid 14. dokido 15. dokidok 16. dokidoki 17. do 18. dok 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. 字符串 "dada" 在 "dad" 中没有出现； 6. 字符串 "doki" 在 "doki" 中出现在位置 $[1]$； 7. 字符串 "ok" 在 "doki" 中出现在位置 $[2]$； 8. 字符串 "doki" 在 "dokidoki" 中出现在位置 $[1, 5]$； 9. 字符串 "doki" 在 "dokidok" 中出现在位置 $[1]$； 10. 字符串 "d" 在 "d" 中出现在位置 $[1]$； 11. 字符串 "a" 在 "d" 中没有出现； 12. 字符串 "doki" 在 "dokidoki" 中出现在位置 $[1, 5]$。 由 ChatGPT 4.1 翻译