分数: 575 点
问题陈述
给你一个字符串 S 由小写英文字母组成。
你还得到 Q 查询按顺序处理。的 i第查询描述如下: 给出由小写英文字母组成的
- 一个字符串 T_i 。打印子串的数量 S 等于 T_i。如果两个子字符串取自不同的位置,即使它们作为字符串相等,它们也会被区分。
约束
- 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- 第一个字符。
- 对于第一个查询,四个子字符串 S 等于
i: S[2:2], S[5:5], S[7:7], S[10:10]. - 对于第二个查询,三个子字符串 S 等于
s: S[3:3], S[4:4], S[6:6]. - 对于第三个查询,没有子字符串 S 匹配
a. - 对于第四个查询,两个子字符串 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