#P17642. [ICPC 2019 Yinchuan R] Largest Common Submatrix
[ICPC 2019 Yinchuan R] Largest Common Submatrix
Problem Description
You are given two matrices, and the elements of each matrix are ranged from to and pairwise distinct. You need to find the common submatrix with the largest size between these two matrices.
Example:
Matrix :
$$\begin{array}{ccc} 1 & 2 & 3\\ 4 & 5 & 6\\ 8 & 7 & 9\\ \end{array}$$Matrix :
$$\begin{array}{ccc} 5 & 6 & 1\\ 7 & 9 & 3\\ 2 & 4 & 8\\ \end{array}$$Largest common submatrix:
Input Format
The first line of input contains two integers and , denoting the number of rows and columns of each matrix.
Each of the next lines contain integers per line, denoting the first matrix . And again, each of the next lines contains integers per line, denoting the second matrix .
It is guaranteed that , and $a_{i_1,j_1} \ne a_{i_2,j_2} \wedge b_{i_1,j_1} \ne b_{i_2,j_2}$ always holds for each pair of and , where .
Output Format
Output an integer representing the size of the largest common submatrix.
3 4
5 6 7 8
1 2 3 4
9 10 11 12
5 6 8 7
1 2 4 3
12 11 10 9
4
Hint
Largest common submatrix in the sample test:
$$\displaystyle \begin{array}{cc} 5 & 6\\ 1 & 2\\ \end{array}$$