如何查找不同子矩阵的数量？

我试图从spoj解决问题DSUBMTR，它要求计算给定矩阵的不同子矩阵。我尝试使用哈希表（STL MAP），但是这种方法是O（因为NM（NM）），因此超时。请注意，给定的矩阵只包含字母。如何查找不同子矩阵的数量？

我想提供一些提示/指示如何解决这些问题。

2014-07-10 Algotest

可能是某种分区。例如，找到相等的a * b子矩阵，那么对于每组相等的子矩阵，只需要比较一个额外的列就可以得到等于a *（b + 1）个子矩阵的组。考虑到组的大小，很容易计算不同子矩阵的数量。 – Nabb

请给我一些关于实现的提示，因为我也有这个想法，但是我的实现没有更好的时间复杂性。 – Algotest

这真的是一个很好的食物的思想的东西。我脑海中想的是使用子矩阵的字母表的ASCII值，并按照只为该特定子矩阵生成唯一值的方式排列它们的值。例如，如果矩阵是[（A，B，C）;（A，A，A）]，那么对于子矩阵[（A，B）;（A，A）]，可以使用ASCII(A)*1000000000+ASCII(B)*1000000+ASCII(A)*1000+ASCII(A)作为这个特殊的子矩阵的唯一值（它虽然不是一个适当的公式，但我希望你能想到更合适的数学方法）。所以，现在你可以将它们散列成散列表。对所有子矩阵应用此公式，并查看散列表上的冲突，并忽略重复的冲突。然后计算哈希表中填充位置的数量。

来源

2014-07-10 13:29:36

你可以提出一个更好的方案，因为尺寸高达128，并且你所建议的方案在这个范围内不是消耗性的。 – Algotest

@Algotest因为只存在26×2的字母表，所以你可以使用它们对应的两位数值来生成一个唯一的子矩阵值。由于您只需比较相同长度×宽度的子矩阵，因此对于不同的子矩阵您将具有不同的值。对所有可能的子矩阵大小做这件事。 –

将会有128×128个子矩阵。我不知道你将如何生成每个唯一的ID。如果可能的话，请添加一个代码片段。 – Algotest

如何查找不同子矩阵的数量？

回答

相关问题