← 返回题目列表

AtCoder · abc362_g

G. 计数子串查询

中文机器翻译题面 查看原题

分数: 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