AtCoder Beginner Contest 054
B
Template Matching
AtCoder
⌀ 893
原题
← AC →
翻译中…

Problem Statement

翻译中…

You are given an image $A$ composed of $N$ rows and $N$ columns of pixels, and a template image $B$ composed of $M$ rows and $M$ columns of pixels. A pixel is the smallest element of an image, and in this problem it is a square of size $1×1$. 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 $A$ is given as $N$ strings $A_1,...,A_N$. The $j$-th character in the string $A_i$ corresponds to the pixel at the $i$-th row and $j$-th column of the image $A$ $(1≦i,j≦N)$. Similarly, the template image $B$ is given as $M$ strings $B_1,...,B_M$. The $j$-th character in the string $B_i$ corresponds to the pixel at the $i$-th row and $j$-th column of the template image $B$ $(1≦i,j≦M)$.

翻译中…

Determine whether the template image $B$ is contained in the image $A$ when only parallel shifts can be applied to the images.

翻译中…

Constraints

翻译中…
  • $1≦M≦N≦50$
  • $A_i$ is a string of length $N$ consisting of # and ..
  • $B_i$ is a string of length $M$ consisting of # and ..
翻译中…

Input

翻译中…

The input is given from Standard Input in the following format:

翻译中…

N M
A_1
A_2
:
A_N
B_1
B_2
:
B_M

翻译中…

Output

翻译中…

Print Yes if the template image $B$ is contained in the image $A$. Print No otherwise.

翻译中…

样例

Input #1
3 2
#.#
.#.
#.#
#.
.#
Output #1
Yes
The template image $B$ is identical to the upper-left $2 × 2$ subimage and the lower-right $2 × 2$ subimage of $A$. Thus, the output should be `Yes`.
Input #2
4 1
....
....
....
....
#
Output #2
No
The template image $B$, composed of a black pixel, is not contained in the image $A$ composed of white pixels.
题目信息
题号
abc054_b
时间限制
2 s
内存限制
256 MB

题面与样例版权归 AtCoder 及出题人所有;中文翻译由 AI 生成(CI 管线),如有出入请以原文为准。