[ABC362] G - Count Substring Query

G - Count Substring Query

Time Limit: 3 sec / Memory Limit: 1024 MB

分数: 575 分

题面

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

还有 个查询需要按顺序处理。第 个查询描述如下：

• 给定一个由小写英文字母组成的字符串 。输出与 相等的 的子串数量。如果两个子串来自不同的位置，即使它们在作为字符串时相等，也会被区分开。

限制条件

• 和 均为由小写英文字母组成的字符串。
• 为整数。

---

输入

输入从标准输入给出，格式如下：

输出

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

---

输入样例 1

missisippi
5
i
s
a
is
missisippi

输出样例 1

4
3
0
2
1

设 表示 中从第 个字符到第 个字符的子串。

• 对于第 1 个查询， 有四个与 i 相等的子串：。
• 对于第 2 个查询， 有三个与 s 相等的子串：。
• 对于第 3 个查询， 中无与 a 相等的子串。
• 对于第 4 个查询， 有两个与 is 相等的子串：。
• 对于第 5 个查询， 有一个与 missisippi 相等的子串：。

---

输入样例 2

aaaaaa
6
a
aa
aaa
aaaa
aaaaa
aaaaaa

输出样例 2

6
5
4
3
2
1