Hide

Problem B
Ascii Art(Easy)

\includegraphics[scale=0.5]{joan} Joan is a hard-core OS programmer who insists on using a command-line terminal for everything. She really enjoys the monospace font that it has. When she writes documents (Mostly man pages) she illustrates them using ASCII art images. That is to say, her images are composed of a paragraph of ASCII characters in such a way that it looks like a picture.

Over time, Joan has made a lot of pictures, and wants to serch her pictures to see if she’s used the same ASCII characters elsewhere. In otherwords, Joan wants to know whether a sample image contains a given template image. She has tasked you with writing the comparison program.

Joan is very creative, so in every one of her files, her images contain a wide variety of ASCII characters dispersed somewhat evenly about the monochrome canvas.

Input

The first line of the input contains four integers $W_ S, H_ S, W_ T, H_ T$ where $0<W_ S,H_ S<=1000, 0<W_ T<=W_ S, 0<H_ T<=H_ S$.

This is followed by a sample ASCII image comprised of $H_ S$ lines containing $W_ S$ characters. Then follow $H_ T$ lines containing $W_ T$ characters that comprise the template image.

Output

If you find the entire template image in the sample image, your program should output two integers $X$ and $Y$ on one line, where $(X, Y)$ is the position of the top left character of the top-most, left-most match. If such a match does not exist, your program will output "no match".

Positions on the image start from $(0,0)$ at the top left and continue until $(W_ S, H_ S)$. Assume $0<=X<=W_ S-W_ T$ and $0<=Y<=H_ S-H_ T$.

Sample Input 1 Sample Output 1
42 11 4 3
#----------------------------------------#
# ______________________________________ #
#/           Does an ASCII cow          \#
#\         produce Unicode milk?        /#
# -------------------------------------- #
#       \   ^__^                         #
#        \  (oo)\_______                 #
#           (__)\       )\/\             #
#               ||----w |                #
#               ||     ||                #
#----------------------------------------#
^__^
(oo)
(__)

12 5
Sample Input 2 Sample Output 2
14 8 2 1
*------------*
| /))))))))) |
|//) __   __\|
|C==/_o|^|o_\|
||      _\  )|
| \   .--. / |
|_/`-. __./_ |
*------------*
<3
no match

Please log in to submit a solution to this problem

Log in