检查多维数组是否包含另一个多维数组的算法？

Question

假设我有两个深度相等的多维数组，例如：

[ [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9] ]

和

[ [2, 3],
  [5, 6] ]

我可以遵循什么样的算法来确定后者是否是前者的连续子数组？

以上面的例子为例，就是：

还有这对 3d 数组：

[ [ [4, 6],
    [5, 7] ],
  [ [2, 8],
    [9, 3] ] ]

[ [ [4, 6] ],
  [ [2, 8] ] ]

另一种解释方法是，通过重复从第一个数组的某个维度中删除第一个或最后一个项目，您最终将获得目标数组。

Answer 1

Rabin -Karp字符串搜索算法可以扩展到多个维度来解决这个问题。

假设您的模式数组是 M 行 x N 列：

1. 使用任何滚动哈希函数（例如多项式哈希），首先用该列的哈希替换模式数组的每一列，将其减少到一维。然后散列剩余的行。这将是您的模式哈希。

2. 现在，使用目标数组中的滚动哈希将行 >= M 中的所有值替换为这些值的哈希值及其上方的 M-1 值。

3. 然后，类似地用这些值和左侧 N-1 值的哈希值替换列 >= N-1 中的所有剩余值。

4. 最后，在结果矩阵中找到模式哈希的任何实例。当您找到一个时，请与您的模式数组进行比较，看看它是否真正匹配。

该算法可以扩展到任意多个维度，并且与简单的 Rabin-Karp 一样，如果维度数恒定，则需要 O(N)预期时间。