← 返回题目列表

Codeforces · 1016/B

B. 段出现次数

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

给定两个字符串 $$$s$$$ 和 $$$t$$$,两者均仅包含小写拉丁字母。

子串$$$s[l..r]$$$ 是字符$$$s_l, s_{l + 1}, \dots, s_r$$$ 不改变顺序得到的字符串。

字符串 $$$b$$$ 中字符串 $$$a$$$ 的每次出现都是一个位置 $$$i$$$ ($$$1 \le i \le |b| - |a| + 1$$$),使得 $$$b[i..i + |a| - 1] = a$$$ ($$$|a|$$$ 是字符串 $$$a$$$ 的长度)。

系统会向您询问 $$$q$$$ 查询:对于第 $$$i$$$ 查询,您需要计算子字符串 $$$s[l_i..r_i]$$$ 中字符串 $$$t$$$ 的出现次数。

输入

第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$q$$$ ($$$1 \le n, m \le 10^3$$$, $$$1 \le q \le 10^5$$$) — 分别是字符串 $$$s$$$ 的长度、字符串 $$$t$$$ 的长度和查询次数。

第二行是字符串 $$$s$$$ ($$$|s| = n$$$),仅由小写拉丁字母组成。

第三行是字符串 $$$t$$$ ($$$|t| = m$$$),仅由小写拉丁字母组成。

接下来的 $$$q$$$ 行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) — 第 $$$i$$$ 查询的参数。

输出

打印 $$$q$$$ 行 — 第 $$$i$$$ 行应包含第 $$$i$$$ 查询的答案,即字符串 $$$t$$$ 在子字符串 $$$s[l_i..r_i]$$$ 中出现的次数。

示例

输入 #1

10 3 4
codeforces
for
1 3
3 10
5 6
5 7

输出 #1

0
1
0
1

输入 #2

15 2 3
abacabadabacaba
ba
1 15
3 4
2 14

输出 #2

4
0
3

输入 #3

3 5 2
aaa
baaab
1 3
1 1

输出 #3

0
0

注意

在第一个示例中,查询分别是子字符串:“cod”、“deforces”、“fo”和“for”。