CF1252D.Find String in a Grid

You have a grid $G$ containing $R$ rows (numbered from $1$ to $R$, top to bottom) and $C$ columns (numbered from $1$ to $C$, left to right) of uppercase characters. The character in the $r^{th}$ row and the $c^{th}$ column is denoted by $G_{r, c}$. You also have $Q$ strings containing uppercase characters. For each of the string, you want to find the number of occurrences of the string in the grid.

An occurrence of string $S$ in the grid is counted if $S$ can be constructed by starting at one of the cells in the grid, going right $0$ or more times, and then going down $0$ or more times. Two occurrences are different if the set of cells used to construct the string is different. Formally, for each string $S$, you would like to count the number of tuples $\langle r, c, \Delta r, \Delta c \rangle$ such that:

• $1 \le r \le R$ and $r \le r + \Delta r \le R$
• $1 \le c \le C$ and $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$ 行（从上到下编号为 $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}$

Input begins with a line containing three integers: $R$ $C$ $Q$ ($1 \le R, C \le 500$; $1 \le Q \le 200\,000$) representing the size of the grid and the number of strings, respectively. The next $R$ lines each contains $C$ uppercase characters representing the grid. The $c^{th}$ character on the $r^{th}$ line is $G_{r, c}$. The next $Q$ lines each contains a string $S$ containing uppercase characters. The length of this string is a positive integer not more than $200\,000$. The sum of the length of all $Q$ strings combined is not more than $200\,000$.

输入的第一行包含三个整数：$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$。

For each query in the same order as input, output in a line an integer representing the number of occurrences of the string in the grid.

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

Explanation for the sample input/output #1

• There are $2$ occurrences of "ABC", represented by the tuples $\langle 1, 1, 1, 1 \rangle$ and $\langle 1, 1, 0, 2 \rangle$.
• There are $3$ occurrences of "BC", represented by the tuples $\langle 1, 2, 0, 1 \rangle$, $\langle 1, 2, 1, 0 \rangle$, and $\langle 2, 1, 0, 1 \rangle$.
• There is $1$ occurrence of "BD", represented by the tuple $\langle 2, 1, 1, 0 \rangle$.
• There is no occurrence of "AC".
• There are $2$ occurrences of "A", represented by the tuples $\langle 1, 1, 0, 0 \rangle$ and $\langle 3, 2, 0, 0 \rangle$.

样例输入/输出 #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$。