103626: [Atcoder]ABC362 G - Count Substring Query

Problem Statement

You are given a string $S$ consisting of lowercase English letters.

You are also given $Q$ queries to process sequentially. The $i$-th query is described as follows:

• A string $T_i$ consisting of lowercase English letters is given. Print the number of substrings of $S$ that equal $T_i$. Two substrings are distinguished if they are taken from different positions, even if they are equal as strings.

Constraints

• $1 \leq |S| \leq 5 \times 10^5$
• $1 \leq Q \leq 5 \times 10^5$
• $1 \leq |T_i| \leq |S|$
• $\displaystyle \sum_{i=1}^Q |T_i| \leq 5 \times 10^5$
• $S$ and $T_i$ are strings consisting of lowercase English letters.
• $Q$ is an integer.

Input

The input is given from Standard Input in the following format:

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

Output

Print $Q$ lines. The $i$-th line should contain the answer to the $i$-th query.

Sample Input 1

missisippi
5
i
s
a
is
missisippi

Sample Output 1

4
3
0
2
1

Let $S[l:r]$ denote the substring of $S$ from the $l$-th character through the $r$-th character.

• For the 1st query, four substrings of $S$ equal i: $S[2:2], S[5:5], S[7:7], S[10:10]$.
• For the 2nd query, three substrings of $S$ equal s: $S[3:3], S[4:4], S[6:6]$.
• For the 3rd query, no substrings of $S$ match a.
• For the 4th query, two substrings of $S$ equal is: $S[2:3], S[5:6]$.
• For the 5th query, one substring of $S$ equals missisippi: $S[1:10]$.

Sample Input 2

aaaaaa
6
a
aa
aaa
aaaa
aaaaa
aaaaaa

Sample Output 2

6
5
4
3
2
1

问题陈述

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

你还依次要处理$Q$个查询。第$i$个查询描述如下：

• 给出一个由小写英文字母组成的字符串$T_i$。打印等于$T_i$的$S$的子串的数量。如果两个子串取自不同的位置，即使它们作为字符串是相等的，也被视为不同。

约束条件

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

输入

输入从标准输入以下格式给出：

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

输出

打印$Q$行。第$i$行应包含对第$i$个查询的答案。

示例输入1

missisippi
5
i
s
a
is
missisippi

示例输出1

4
3
0
2
1

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

• 对于第1个查询，四个子串$S$等于i：$S[2:2], S[5:5], S[7:7], S[10:10]$。
• 对于第2个查询，三个子串$S$等于s：$S[3:3], S[4:4], S[6:6]$。
• 对于第3个查询，没有子串$S$匹配a。
• 对于第4个查询，两个子串$S$等于is：$S[2:3], S[5:6]$。
• 对于第5个查询，一个子串$S$等于missisippi：$S[1:10]$。

示例输入2

aaaaaa
6
a
aa
aaa
aaaa
aaaaa
aaaaaa

示例输出2

6
5
4
3
2
1