306793: CF1252D. Find String in a Grid
Memory Limit:256 MB
Time Limit:5 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Find String in a Grid
题意翻译
现有一个由大写字母构成的$n$行$m$列矩阵。 定义一个**L型路径**为,从矩阵某个位置开始,先向右走若干步,再向下走若干步,且不离开矩阵边界的路径。 定义一个**L型字符串**为对应的L型路径上字符依次连接起来组成的字符串。 现给定$q$次询问,每次给一个大写字母组成的字符串$S$,询问矩阵中包含多少个等于$S$的L型字符串。 $n\le 500, m\le 500, q\le 2\times 10^5$,所有查询的字符串长度之和$\le 2\times 10^5$。 _Translated by Caro23333_题目描述
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.
输入输出样例
输入样例 #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