33OJ
登录 注册

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

[ICPC 2019 Yinchuan R] Largest Common Submatrix

题目描述

给定两个 n×mn \times m 的矩阵,每个矩阵中的元素均为 11 到 n×mn \times m 之间的整数且两两不同。你需要找出这两个矩阵之间最大的公共子矩阵。

例子:

矩阵 AA:

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

矩阵 BB:

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

最大公共子矩阵:

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

输入格式

第一行输入包含两个整数 n (1≤n≤1000)n~(1 \le n \le 1000) 和 m (1≤m≤1000)m~(1 \le m \le 1000),表示每个矩阵的行数和列数。

接下来的 nn 行,每行包含 mm 个整数,表示第一个矩阵 A=(ai,j)n×mA=(a_{i,j})_{n\times m}。再接下来的 nn 行,每行包含 mm 个整数,表示第二个矩阵 B=(bi,j)n×mB=(b_{i,j})_{n\times m}。

保证 1≤ai,j,bi,j≤n×m1 \le a_{i,j}, b_{i,j} \le n \times m,且对于任意两对不同的下标 (i1,j1)(i_1, j_1) 和 (i2,j2)(i_2, j_2),总有 ai1,j1≠ai2,j2a_{i_1,j_1} \ne a_{i_2,j_2} 以及 bi1,j1≠bi2,j2b_{i_1,j_1} \ne b_{i_2,j_2}。

输出格式

输出一个整数,表示最大公共子矩阵的大小。

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

提示

样例测试中的最大公共子矩阵:

$$\displaystyle \begin{array}{cc} 5 & 6\\ 1 & 2\\ \end{array}$$

翻译由 DeepSeek V4 Pro 完成