A13015. 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}$
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.
输入输出样例
输入 #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
说明/提示
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$ .
- 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$ .