ZOJ Problem Set - 3367
With the development of modern colorful copying and printing hardware as well as image processing software the problem of counterfeit money has become critical. To prevent spreading of the counterfeit money, the financial organizations force image processing software developers to insert special functions into their software that would prevent users from operating with images of banknotes.
You are working on a prototype of such system and are asked to implement the routine that would check whether the loaded image is the modified image of a banknote. To make a first test you decided to find a largest common rectangle on the loaded image and the image of the banknote and if it is large enough, report it to the other routine, that would make a detailed check.
Given two rectangular images find their common rectangle with the largest area.
The first line of the input file contains m1 and n1 --- the height and the width of the first image. The next m1 lines contain n1 letters each --- different letters correspond to different colors of the image. Only capital letters of the English alphabet are used.
The rest of the file describes the second image in the same format. Both width and height of each image do not exceed 40.
There are multiple cases. Process to the end of file.
On the first line of the output file print the height and the width of the largest common rectangle of the two images. On the second line print the coorindates of its upper-left corner in the first rectangle (first coordinate is the row, second is the column, rows are numbered from top to bottom, columns --- from left to right). On the third line print the coordinates of its upper-left corner in the second rectangle.
If no common rectangle exists, print two zeroes on the first and the only line of the output file.
3 4 ABAB CBDC BACD 4 3 BAB BDB ACD ABA 1 1 A 1 1 B
3 2 1 2 1 1 0 0
Author: Andrew Stankevich
Source: Andrew Stankevich's Contest #11