#ABC054B. Template Matching
Template Matching
Problem Statement
You are given an image composed of rows and columns of pixels, and a template image composed of rows and columns of pixels.
A pixel is the smallest element of an image, and in this problem it is a square of size .
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 is given as strings .
The -th character in the string corresponds to the pixel at the -th row and -th column of the image .
Similarly, the template image B is given as strings .
The -th character in the string corresponds to the pixel at the -th row and -th column of the template image .
Determine whether the template image is contained in the image when only parallel shifts can be applied to the images.
Constraints
- is a string of length consisting of
#
and.
. - is a string of length consisting of
#
and.
.
Input
The input is given from Standard Input in the following format:
N M A1 A2 : AN B1 B2 : BM
Output
Print Yes
if the template image is contained in the image . Print No
otherwise.
Samples
3 2
#.#
.#.
#.#
#.
.#
Yes
The template image is identical to the upper-left subimage and the lower-right subimage of . Thus, the output should be Yes
.
4 1
....
....
....
....
#
No
The template image , composed of a black pixel, is not contained in the image composed of white pixels.