更大的矩阵中最大的等于子矩阵 [英] Largest equal submatrices in bigger matrix

问题描述

假设你有一个矩阵的高度h和宽度w（h，w <= 500）你必须找到两个相同大小的子矩阵是相等的。任何解决方案？

Suppose you have one matrix of height h and width w (h,w <= 500) You have to find two submatrices of same size that are equal. Any idea for solving ?

推荐答案

您可以枚举所有向量（ - h< dh< h，0< ; = dw 在 O（hw）中。对于每个这样的向量，通过向量（dh，dw）转换矩阵，并从原始向量中减去转换的矩阵。在它们重叠的范围内，您想要找到具有最大面积的零矩形。您可以使用

You can enumerate all vectors (-h < dh < h, 0 <= dw < w) in O(hw). For each such vector, translate the matrix by the vector (dh, dw) and subtract the translated matrix from the original one. In the range where they overlap you want to find the rectangle of zeroes that has the largest area. You can use a linear time algorithm to do that.

运行时： O（w ² h ² ）

一种更实际的方法是散列所有子矩阵，并以这种方式检查重复。这将有相同的预期运行时。

A more pragmatic approach would be to hash all submatrices and check for duplicates that way. This would have the same expected runtime.

这篇关于更大的矩阵中最大的等于子矩阵的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！