子串计数查询

题目描述

给定由小写英文字母组成的字符串 $S$。

另外给定 $Q$ 个需要依次处理的查询。第 $i$ 个查询如下:

给出由小写英文字母组成的字符串 $T_i$,输出 $S$ 中等于 $T_i$ 的子串数量。两个子串即使作为字符串相同,只要来自不同位置即视为不同。

输入格式

输入按以下格式从标准输入给出:

$S$
$Q$
$T_1$
$T_2$
$\vdots$
$T_Q$

输出格式

输出 $Q$ 行。第 $i$ 行应包含第 $i$ 个查询的答案。

样例

missisippi
5
i
s
a
is
missisippi

4
3
0
2
1

设 $S[l:r]$ 表示 $S$ 中从第 $l$ 个字符到第 $r$ 个字符的子串。

第 1 个查询:S 中有 4 个子串等于 i,即 $S[2:2]$、$S[5:5]$、$S[7:7]$、$S[10:10]$。

第 2 个查询:S 中有 3 个子串等于 s,即 $S[3:3]$、$S[4:4]$、$S[6:6]$。

第 3 个查询:S 中没有等于 a 的子串。

第 4 个查询:S 中有 2 个子串等于 is,即 $S[2:3]$、$S[5:6]$。

第 5 个查询:S 中有 1 个子串等于 missisippi,即 $S[1:10]$。

aaaaaa
6
a
aa
aaa
aaaa
aaaaa
aaaaaa

6
5
4
3
2
1

数据范围

• $1 \le |S| \le 5 \times 10^5$
• $1 \le Q \le 5 \times 10^5$
• $1 \le |T_i| \le |S|$
• $\displaystyle \sum_{i=1}^Q |T_i| \le 5 \times 10^5$
• $S$ 和 $T_i$ 是由小写英文字母组成的字符串。
• $Q$ 是整数。