Count Substring Query

题目描述

给你一个由小写英文字母组成的字符串 $S$。 同时给出 $Q$ 个需要依次处理的查询。第 $i$ 个查询描述如下：

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

输入格式

输入从标准输入按以下格式给出： $S$ $Q$ $T_1$ $T_2$ $\vdots$ $T_Q$

输出格式

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

missisippi
5
i
s
a
is
missisippi

4
3
0
2
1

aaaaaa
6
a
aa
aaa
aaaa
aaaaa
aaaaaa

6
5
4
3
2
1

提示

$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[l:r]$ 表示字符串 $S$ 从第 $l$ 个字符到第 $r$ 个字符的子串。

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

标签: AtCoder|abc362G

来源

AtCoder|abc362G