← 返回题目列表

AtCoder · abc054_b

B. 模板匹配

中文机器翻译题面 查看原题

分数: 200 点

问题陈述

给你一张图片 A 组成 N 行和 N 像素列和模板图像 B 组成 M 行和 M 像素列。
像素是图像的最小元素,在这个问题中它是一个大小的正方形 1×1.
此外,给定的图像是二值图像,每个像素的颜色是白色或黑色。

在输入中,每个像素都由一个字符表示: . 对应于白色像素,并且 # 对应于黑色像素。
图像 A 给出为 N 字符串 A_1,...,A_N.
的 j- 字符串中的第一个字符 A_i 对应于 i第行和 j图像的第列 A (1≦i,j≦N).
同样,模板图像 B 给出为 M 字符串 B_1,...,B_M.
的 j- 字符串中的第一个字符 B_i 对应于 i第行和 j模板图像的第列 B (1≦i,j≦M).

判断模板图像是否 图片中包含 B 包含在图像中 A 当只能对图像应用平行移动时。

约束

  • 1≦M≦N≦50
  • A_i 是一个长度为的字符串 N 组成 # 和 ..
  • B_i 是一个长度为的字符串 M 组成 # 和 ..

输入

输入由标准输入按以下格式给出:

N M
A_1
A_2
:  
A_N
B_1
B_2
:  
B_M

输出

打印 Yes 如果模板图像 B 包含在图像中 A。打印 No 否则。


样本输入 1

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

示例输出 1

Yes

模板图像 B 与左上角相同 2 × 2 子图像和右下角 2 × 2 的子图像 A。因此,输出应该是 Yes.


示例输入 2

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

示例输出 2

No

模板图像 B由黑色像素组成,不包含在图像中 A 由白色像素组成。