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}$

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$ .

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$ .