#ABC054B. Template Matching

Template Matching

题目描述

You are given an image AA composed of NN rows and NN columns of pixels, and a template image BB composed of MM rows and MM columns of pixels.
A pixel is the smallest element of an image, and in this problem it is a square of size 1111.
Also, the given images are binary images, and the color of each pixel is either white or black.

In the input, every pixel is represented by a character: . corresponds to a white pixel, and # corresponds to a black pixel.
The image AA is given as NN strings A1,...,ANA_1,...,A_N.
The jj-th character in the string AiA_i corresponds to the pixel at the ii-th row and jj-th column of the image AA (1i,jN)(1≦i,j≦N).
Similarly, the template image BB is given as MM strings B1,...,BMB_1,...,B_M.
The jj-th character in the string BiB_i corresponds to the pixel at the ii-th row and jj-th column of the template image BB (1i,jM)(1≦i,j≦M).

Determine whether the template image BB is contained in the image AA when only parallel shifts can be applied to the images.

给你一幅由 NN 行和 NN 列像素组成的图像 AA 和一幅由 MM 行和 MM 列像素组成的模板图像 BB
像素是图像中最小的元素,在本问题中,像素是大小为 1111 的正方形。
此外,给定的图像是二值图像,每个像素的颜色为白色或黑色。

在输入中,每个像素用一个字符表示:.对应一个白色像素,#对应一个黑色像素。
图像 AA 的字符串为 NNA1,...,ANA_1,...,A_N
字符串 AiA_i 中的 jj -th 字符对应图像 AAii -th 行和 jj -th 列的像素。 (1i,jN)(1≦i,j≦N) .
同样,模板图像 BB 的字符串为 MM B1,...,BMB_1,...,B_M
字符串 BiB_i 中的 jj -th 字符对应模板图像 BBii -th 行和 jj -th 列的像素。 (1i,jM)(1≦i,j≦M) .

在只能对图像进行平行移动的情况下,确定模板图像 BB 是否包含在图像 AA 中。

输入格式

输入内容按以下格式标准输入:

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

输出格式

如果模板图像 BB 包含在图像 AA 中,则打印 。否则打印

样例 #1

样例输入 #1

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

样例输出 #1

Yes

样例 #2

样例输入 #2

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

样例输出 #2

No

说明

数据规模与约定

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

样例 11 解释

模板图像 BBAA 的左上方 222 2 子图像和右下方 222 2 子图像完全相同。因此,输出结果应为 "是"。

样例 22 解释

由黑色像素组成的模板图像 BB 不包含在由白色像素组成的图像 AA 中。