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:
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.
3 3 5 ABC BCD DAB ABC BC BD AC A
2 3 1 0 2
2 3 3 AAA AAA A AAA AAAAA
6 4 0
Explanation for the sample input/output #1
Name |
---|