题目分析

求两个 $n \times n$ 矩阵的最大公共正方形子矩阵的边长。

---

算法思路：哈希 + 二分查找

核心思想

• 枚举可能的正方形边长 $len$
• 使用滚动哈希计算所有 $len \times len$ 子矩阵的哈希值
• 检查两个矩阵是否存在相同哈希值的子矩阵

---

哈希计算

对于 $len \times len$ 的子矩阵，哈希值计算为：

$$H = \sum_{i=x}^{x+len-1} \sum_{j=y}^{y+len-1} M[i][j] \cdot base^{(len-1-i+x) \times len + (len-1-j+y)} $$

实际代码采用递推计算：

ull h = 0;
for(int x=i; x<=i+len-1; x++)
    for(int y=j; y<=j+len-1; y++)
        h = h * base + a[x][y];

---

算法步骤

1. 预处理：读入两个 $n \times n$ 矩阵
2. 从大到小枚举边长：$len = n, n-1, \dots, 1$
3. 检查函数 check(len)：
   • 计算矩阵 A 所有 $len \times len$ 子矩阵的哈希值，存入哈希表
   • 计算矩阵 B 所有 $len \times len$ 子矩阵的哈希值
   • 检查是否存在相同哈希值
4. 输出：找到的最大可行边长

---

复杂度分析

• 子矩阵数量：$O(n^2)$ 个
• 哈希计算：每个子矩阵 $O(len^2)$
• 总复杂度：$O(n^4)$ 最坏情况
• 实际效率：在 $n \leq 50$ 时可行（$50^4 = 6.25 \times 10^6$）

---

样例验证

输入：

n = 3
矩阵 A:    矩阵 B:
1 2 3     5 6 7  
4 5 6     8 9 1
7 8 9     2 3 4

处理过程：

• $len = 3$：无匹配
• $len = 2$：找到公共子矩阵 $\begin{bmatrix}5&6\\8&9\end{bmatrix}$
• 输出：2

与样例一致。

---

算法优势

• 简洁高效：哈希避免暴力比较
• 正确性：枚举所有可能边长
• 可行性：在数据范围内运行良好

该解法通过哈希技术高效解决了最大公共子矩阵查找问题。