← 返回题目列表

Codeforces · 1252/D

D. 在网格中查找字符串

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

您有一个网格 $$$G$$$,其中包含大写字符的 $$$R$$$ 行(编号从 $$$1$$$ 到 $$$R$$$,从上到下)和 $$$C$$$ 列(编号从 $$$1$$$ 到 $$$C$$$,从左到右)。 $$$r^{th}$$$ 行和 $$$c^{th}$$$ 列中的字符由 $$$G_{r, c}$$$ 表示。您还有包含大写字符的 $$$Q$$$ 字符串。对于每个字符串,您想要查找该字符串在网格中出现的次数。

如果 $$$S$$$ 可以通过从网格中的一个单元格开始,向右 $$$0$$$ 或多次,然后向下 $$$0$$$ 或多次来构造,则对网格中字符串 $$$S$$$ 的出现进行计数。如果用于构造字符串的单元格集合不同,则两次出现的情况不同。正式地,对于每个字符串 $$$S$$$,您希望计算元组 $$$\langle r, c, \Delta r, \Delta c \rangle$$$ 的数量,这样:

- $$$1 \le r \le R$$$ 和 $$$r \le r + \Delta r \le R$$$
- $$$1 \le c \le C$$$ 和 $$$c \le c + \Delta c \le C$$$
- $$$S = G_{r, c} G_{r, c + 1} \点 G_{r, c + \Delta c} G_{r + 1, c + \Delta c} \点 G_{r + \Delta r, c + \Delta c}$$$

输入

输入以包含三个整数的行开头: $$$R$$$ $$$C$$$ $$$Q$$$ ($$$1 \le R, C \le 500$$$; $$$1 \le Q \le 200\,000$$$) 分别表示网格的大小和字符串的数量。接下来的 $$$R$$$ 行每行包含表示网格的 $$$C$$$ 大写字符。 $$$r^{th}$$$ 行上的 $$$c^{th}$$$ 字符是 $$$G_{r, c}$$$。接下来的 $$$Q$$$ 行每行包含一个包含大写字符的字符串 $$$S$$$。该字符串的长度是一个不超过$$$200\,000$$$的正整数。所有$$$Q$$$字符串的长度总和不超过$$$200\,000$$$。

输出

对于与输入相同顺序的每个查询,在一行中输出一个整数,表示该字符串在网格中出现的次数。

示例

输入 #1

3 3 5
ABC
BCD
DAB
ABC
BC
BD
AC
A

输出 #1

2
3
1
0
2

输入 #2

2 3 3
AAA
AAA
A
AAA
AAAAA

输出 #2

6
4
0

注意

示例输入/输出#1 的说明

- 有 $$$2$$$ 出现“ABC”,由元组 $$$\langle 1, 1, 1, 1 \rangle$$$ 和 $$$\langle 1, 1, 0, 2 \rangle$$$ 表示。
- 出现 $$$3$$$ 次“BC”,由元组 $$$\langle 1, 2, 0, 1 \rangle$$$、$$$\langle 1, 2, 1, 0 \rangle$$$ 和 $$$\langle 2, 1, 0, 1 \rangle$$$ 表示。
- 有 $$$1$$$ 出现“BD”,由元组 $$$\langle 2, 1, 1, 0 \rangle$$$ 表示。
- 没有出现“AC”。
- “A”出现 $$$2$$$ 次,由元组 $$$\langle 1, 1, 0, 0 \rangle$$$ 和 $$$\langle 3, 2, 0, 0 \rangle$$$ 表示。