题目背景

翻译自 CSES-2103 题。

题目描述

给定一个字符串和多个子串，统计每个子串在字符串中出现的位置数量。

输入格式

第一行包含一个长度为 $n$ 的字符串。

第二行包含一个整数 $k$，表示子串的数量。

接下来有 $k$ 行，每行包含一个子串。

字符串和子串中的字符都由小写字母 $a–z$ 组成。

输出格式

对于每个子串，输出该子串在字符串中出现的位置数量。

样例

aybabtu
3
bab
abc
a

1
0
2

数据范围

• $1 \le n \le 10^5$
• $1 \le k \le 5 \times 10^5$
• 所有子串的总长度最多为 $5 \times 10^5$