大矩阵中最大的相等子矩阵

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

2014-03-19 user3333971

等于意味着子矩阵中的每个元素都相同？ – taocp

矩阵中元素的类型如何？这些数字或可以是字符/字符串？ – Mohan

子矩阵应该最大吗？如果没有，这很容易，你可以检查是否有两个元素具有相同的项目。 –

可以枚举所有矢量（-h < DH <小时，0 < = DW<瓦特）在O（HW）。对于每个这样的矢量，通过矢量（dh，dw）来转换矩阵并从原始矩阵中减去转换后的矩阵。在它们重叠的范围内，您想要查找具有最大面积的零的矩形。您可以使用a linear time algorithm来做到这一点。

运行：O（w^^ h ）

一种更务实的方法是哈希所有子矩阵和重复检查的方式。这将具有相同的预期运行时间。

来源

2014-03-19 00:58:12

h，w <= 500，O（w²h²）会花费太长时间，不是吗（至少对于编程竞赛标准来说）？ –

@JuanLopes：我不知道，根据我的估计，它可能会在一分钟内运行。在比赛中，这肯定会太慢，但也许它不是那种问题 –

我没有看到很多像“高度h和宽度w（h，w <= 500）”外部比赛的陈述：P –

存在比O更好的算法（w h ）。首先考虑一个更简单的版本。给定一个只有小写字母的矩阵M，找到矩阵中的最大子字符串。这个问题等于找到longest common substring在M[0]$1M[1]...M[w-1]，我们在M[i]和M[i+1]之间添加不同的特殊字符。使用suffix array，最长的公共子串问题可以在线性时间内解决，对于这种情况，它可以用O（wh）来解决。

对于最大子矩阵的问题，通过列举所有可能的高度升< = H，在同一时间它可以是减少了的子问题，词典顺序2子带高度l可以由具有高度的子串的顺序继承l-1。

正如@Niklas B解释。在第一次迭代中，我们使用后缀数组来排列矩阵的行后缀。然后在第二步中，我们使用基数排序并重新使用第一次迭代中计算出的等级来排列相邻2行组合的后缀。在第三步中，我们对相邻3行的后缀进行排序等等。我们还可以为每次迭代维护LCP arrays，这样我们就可以使用一次遍历找到出现两次的最长子字符串。

总的来说，这个算法是ø（H 2 瓦特）与线性时间后缀数组构造算法。

来源

2014-03-19 03:04:19

对不起，我可怜的英语，你能理解第一部分吗？ –

是的，我开始看到第二段的含义，但有点难理解。 –

我现在明白了。非常酷的想法，但是真的很难从你的答案中理解：/ –

大矩阵中最大的相等子矩阵

回答

相关问题