#P16689. [ICPC 2019]Jakarta R]Find String in a Grid

[ICPC 2019]Jakarta R]Find String in a Grid

题目描述

给定一个由大写英文字母组成的网格 GG,它有 RR 行和 CC 列:

  • 行从上到下编号为 11 到 RR;
  • 列从左到右编号为 11 到 CC;
  • 第 rr 行第 cc 列的字符记作 Gr,cG_{r,c}。

另外给定 QQ 个仅由大写英文字母组成的字符串。

对于每个查询字符串 SS,请计算它在网格中出现的次数。

一次出现需要按照以下方式构造字符串:

  1. 从网格中的某个单元格出发;
  2. 向右移动零次或多次;
  3. 随后向下移动零次或多次;
  4. 按经过顺序连接所有访问单元格中的字符,得到的字符串必须恰好等于 SS。

移动方向最多发生一次变化:只能先向右,再向下。向右或向下的移动次数都可以为 00。

如果两次构造使用的单元格集合不同,则它们被视为不同的出现。

形式化地,对每个字符串 SS,需要统计满足下列条件的四元组

⟨r,c,Δr,Δc⟩\langle r,c,\Delta r,\Delta c\rangle

的数量:

1≤r≤R,r≤r+Δr≤R,1\le r\le R,\qquad r\le r+\Delta r\le R, 1≤c≤C,c≤c+Δc≤C,1\le c\le C,\qquad c\le c+\Delta c\le C,

并且

$$S= G_{r,c}G_{r,c+1}\cdots G_{r,c+\Delta c} G_{r+1,c+\Delta c}\cdots G_{r+\Delta r,c+\Delta c}.$$

当 Δc=0\Delta c=0 时,路径只向下;当 Δr=0\Delta r=0 时,路径只向右;二者都为 00 时,只使用一个单元格。

输入格式

第一行包含三个整数 R,C,QR,C,Q:

1≤R,C≤500,1\le R,C\le 500, 1≤Q≤200 000,1\le Q\le 200\,000,

分别表示网格的行数、列数和查询字符串数量。

接下来 RR 行,每行包含一个长度为 CC 的大写字母字符串,表示网格。

随后 QQ 行,每行包含一个非空大写字母字符串 SS。

每个查询字符串的长度不超过:

200 000.200\,000.

所有查询字符串的长度总和不超过:

200 000.200\,000.

输出格式

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

样例 1

输入

3 3 5
ABC
BCD
DAB
ABC
BC
BD
AC
A

输出

2
3
1
0
2

样例说明

  • ABC 有 22 次出现,对应:

    $$\langle1,1,1,1\rangle,\qquad \langle1,1,0,2\rangle.$$
  • BC 有 33 次出现,对应:

    $$\langle1,2,0,1\rangle,\quad \langle1,2,1,0\rangle,\quad \langle2,1,0,1\rangle.$$
  • BD 有 11 次出现,对应:

    ⟨2,1,1,0⟩.\langle2,1,1,0\rangle.
  • AC 没有出现。

  • A 有 22 次出现,分别位于单元格 (1,1)(1,1) 和 (3,2)(3,2)。

样例 2

输入

2 3 3
AAA
AAA
A
AAA
AAAAA

输出

6
4
0