CF1252D Find String in a Grid

给定一个包含 $R$ 行（从上到下编号为 $1$ 到 $R$）和 $C$ 列（从左到右编号为 $1$ 到 $C$）的大写字母网格 $G$。第 $r$ 行第 $c$ 列的字符记作 $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} \dots G_{r, c + \Delta c} G_{r + 1, c + \Delta c} \dots 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$ 行第 $c$ 个字符为 $G_{r, c}$。接下来的 $Q$ 行，每行包含一个仅由大写字母组成的字符串 $S$，其长度为正整数且不超过 $200\,000$。所有 $Q$ 个字符串的总长度不超过 $200\,000$。

对于每个询问，按照输入顺序，每行输出一个整数，表示该字符串在网格中出现的次数。

样例输入输出 #1 说明： - "ABC" 有 $2$ 次出现，分别对应四元组 $\langle 1, 1, 1, 1 \rangle$ 和 $\langle 1, 1, 0, 2 \rangle$。 - "BC" 有 $3$ 次出现，分别对应 $\langle 1, 2, 0, 1 \rangle$、$\langle 1, 2, 1, 0 \rangle$ 和 $\langle 2, 1, 0, 1 \rangle$。 - "BD" 有 $1$ 次出现，对应 $\langle 2, 1, 1, 0 \rangle$。 - "AC" 没有出现。 - "A" 有 $2$ 次出现，分别对应 $\langle 1, 1, 0, 0 \rangle$ 和 $\langle 3, 2, 0, 0 \rangle$。 由 ChatGPT 4.1 翻译