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

问题描述

假设你有高度h和宽度一种基质W（H，W＆LT; = 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＆LT; D​​H＆LT; H，0℃= DW＆LT; W）的在 O（HW）的。对于每个这样的载体中，通过该载体转化的矩阵的（DH，DW）的和减去从原来的已翻译的矩阵。在他们重叠的范围要查找零的具有最大面积的矩形。您可以使用<一个href="http://stackoverflow.com/questions/3806520/finding-maximum-size-sub-matrix-of-all-1s-in-a-matrix-having-1s-and-0s">a线性时间算法做到这一点。

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.

运行时： 0（W ² ^ h ² ）的

Runtime: 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屋！