33OJ
登录 注册

#P17642. [ICPC 2019 Yinchuan R] Largest Common Submatrix

[ICPC 2019 Yinchuan R] Largest Common Submatrix

Problem Description

You are given two n×mn \times m matrices, and the elements of each matrix are ranged from 11 to n×mn \times m and pairwise distinct. You need to find the common submatrix with the largest size between these two matrices.

Example:

Matrix AA:

$$\begin{array}{ccc} 1 & 2 & 3\\ 4 & 5 & 6\\ 8 & 7 & 9\\ \end{array}$$

Matrix BB:

$$\begin{array}{ccc} 5 & 6 & 1\\ 7 & 9 & 3\\ 2 & 4 & 8\\ \end{array}$$

Largest common submatrix:

5679\begin{array}{cc} 5 & 6\\ 7 & 9\\ \end{array}

Input Format

The first line of input contains two integers n (1≤n≤1000)n~(1 \le n \le 1000) and m (1≤m≤1000)m~(1 \le m \le 1000), denoting the number of rows and columns of each matrix.

Each of the next nn lines contain mm integers per line, denoting the first matrix A=(ai,j)n×mA=(a_{i,j})_{n\times m}. And again, each of the next nn lines contains mm integers per line, denoting the second matrix B=(bi,j)n×mB=(b_{i,j})_{n\times m}.

It is guaranteed that 1≤ai,j,bi,j≤n×m1 \le a_{i,j}, b_{i,j} \le n \times m, 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 (i1,j1)(i_1, j_1) and (i2,j2)(i_2, j_2), where i1≠i2∨j1≠j2i_1 \ne i_2 \vee j_1 \ne j_2.

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}$$