寻找n×n二进制图像中重复出现的最大矩形图案的算法

好问题！要在n×n的二进制图像里找出重复出现至少两次的最大面积矩形，咱们可以从几个实用的思路和算法入手，下面一步步拆解：

首先得搞清楚目标：我们要找的是两个或多个位置不同，但二进制像素完全一致的矩形，目标是最大化它们的面积（长×宽）。

这是最容易落地且效率不错的方案，核心是把二维问题转化为一维问题处理：

• 步骤1：固定上下边界，压缩列信息
  遍历所有可能的上边界top（从0到n-1），然后让下边界bottom从top开始向下扩展到n-1。对于每一组(top, bottom)，我们把每一列从top到bottom的二进制串转换成一个整数（比如列里的像素是[1,0,1]，就转成二进制数101=5）。这样原本的二维图像就被压缩成了一个长度为n的一维整数数组col_values，每个元素代表对应列在当前上下边界内的“特征值”。

  • 这里可以用位运算加速：当bottom从top往下走时，每一列的特征值可以用前一步的结果左移1位，再加上当前bottom行的该列像素值（0或1），这样每列的更新是O(1)，不用重新遍历top到bottom的所有行。

• 步骤2：在一维数组中找最长重复子数组
  现在问题变成：在col_values里找至少出现两次的连续子数组，子数组的长度就是矩形的宽度w，而矩形的高度h = bottom - top + 1，面积就是h*w。

  • 怎么找重复子数组？用哈希表记录每个连续子数组的起始位置：比如遍历每个起始索引left，然后从left开始向右扩展right，把col_values[left..right]的哈希值存入哈希表（可以用滚动哈希来计算子数组的哈希，避免每次拼接字符串）。如果发现某个哈希值已经存在，就计算当前子数组的长度，更新最大面积。
  • 优化：如果当前计算的h*(right-left+1)已经小于等于已知的最大面积，就可以提前终止这个right的扩展，剪枝减少计算量。

如果你的图像比较大，或者最大重复矩形的面积本身就很大，这个方法会更快——因为我们从最大的可能面积开始枚举，一旦找到符合条件的重复矩形，直接返回结果，不用再处理更小的面积：

• 步骤1：枚举可能的面积大小
  从最大的n*n开始，依次往下枚举所有可能的面积值area（比如n*n → n*(n-1) → (n-1)*n → (n-1)*(n-1)…）。对于每个area，找出所有可能的(h, w)组合（满足h*w = area，且h ≤ n，w ≤ n）。

• 步骤2：遍历所有该尺寸的矩形，检查重复
  对每个(h, w)，遍历图像中所有可能的h×w矩形：

  • 把矩形的所有像素按行（或列）拼接成一个二进制字符串，计算它的哈希值（用滚动哈希更高效）。
  • 把哈希值存入哈希表，如果发现某个哈希值已经存在，说明找到了重复的矩形，直接返回当前area作为答案。

• 优势：如果最大的重复矩形存在，我们不需要遍历所有小尺寸的矩形，节省大量时间。

不管用哪种方法，这些技巧都能帮你提升效率：

• 滚动哈希（Rabin-Karp）：避免存储整个矩形的二进制串，而是将其转换成一个固定长度的哈希值，计算和比较都更快。为了减少哈希碰撞，可以用双重哈希（两个不同的哈希函数，只有两个哈希值都相同才认为矩形相同）。
• 剪枝策略：一旦找到当前最大的面积，后续所有小于等于该面积的枚举都可以直接跳过。
• 位运算加速：二进制图像天生适合位运算，比如列特征值的计算、矩形像素的拼接都可以用位运算快速完成。
• 后缀数组优化：如果用方法1，在找最长重复子数组时，可以把col_values转换成字符串，用后缀数组找最长公共子串，这样时间复杂度可以从O(n²)降到O(n log n)，适合更大的n。

• 方法1的时间复杂度：固定上下边界是O(n²)，每个边界下处理列和找重复子数组是O(n²)，总复杂度是O(n⁴)（小n完全没问题）；如果用后缀数组优化，总复杂度降到O(n² log n)，适合n≤100的场景。
• 方法2的时间复杂度：最坏情况是O(n⁴)（比如最大重复矩形是1×1），但平均情况下如果大尺寸重复矩形存在，会快很多。

内容的提问来源于stack exchange，提问作者Dawn17