#abc054b. [abc054_b]Template Matching

[abc054_b]Template Matching

题目描述

给定一个由 NNNN 列像素组成的图像 AA,以及一个由 MMMM 列像素组成的模板图像 BB
像素是图像中最小的元素,在这个问题中它是一个大小为 1×11×1 的正方形。
而且,给定的图像都是二进制图像,每个像素的颜色要么是白色,要么是黑色。

在输入中,每个像素由一个字符表示:. 表示白色像素,# 表示黑色像素。
图像 AA 给出为 NN 个字符串 A1,...,ANA_1,...,A_N
字符串 AiA_i 中的第 jj 个字符对应于图像 AA 的第 ii 行第 jj 列的像素 (1i,jN)(1≦i,j≦N)
类似地,模板图像 BB 给出为 MM 个字符串 B1,...,BMB_1,...,B_M
字符串 BiB_i 中的第 jj 个字符对应于模板图像 BB 的第 ii 行第 jj 列的像素 (1i,jM)(1≦i,j≦M)

确定当只能将图像平行移动时,模板图像 BB 是否包含在图像 AA 中。

约束条件

  • 1MN501≦M≦N≦50
  • AiA_i 是长度为 NN 的字符串,由 #. 组成。
  • BiB_i 是长度为 MM 的字符串,由 #. 组成。

输入

输入以以下格式从标准输入中给出:

NN MM A1A_1 A2A_2 ::
ANA_N B1B_1 B2B_2 ::
BMB_M

输出

如果模板图像 BB 包含在图像 AA 中,请输出 Yes。否则,请输出 No

示例输入 1

3 2
#.#
.#.
#.#
#.
.#

示例输出 1

Yes

模板图像 BB 与图像 AA 的左上角 2×22 × 2 子图和右下角 2×22 × 2 子图完全相同。因此,输出应为 Yes

示例输入 2

4 1
....
....
....
....
#

示例输出 2

No

由于模板图像 BB 仅由一个黑色像素组成,而图像 AA 由白色像素组成,所以模板图像 BB 不包含在图像 AA 中。