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

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] ] ]

另一种解释是，通过反复从第一个数组的维度中删除第一个或最后一个项，最终可以得到目标数组。

- Emanresu a

---

如果您想检查 A ⊆ B 是否成立，您需要在集合论中寻找答案。我无法在 Stackoverflow 上找到合适的标签。我认为这个问题在 https://math.stackexchange.com/ 上会得到更多关注。 - Ted Lyngmo

Answer 1

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

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

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

2. 现在，在目标数组中使用滚动哈希来替换所有行≥M的值，使它们变为它们上面M-1个值的哈希值。

3. 然后，类似地，将所有剩余的列≥N-1的值替换为这些值及其左边的N-1个值的哈希值。

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

此算法可以扩展到您喜欢的任意维度，并且像简单的Rabin-Karp一样，如果维数恒定，则其期望时间复杂度为O(N)。

- Matt Timmermans

Answer 2

简单而朴素的方法是，寻找第一个（0,0）匹配，然后比较子数组。

示例：（Python）

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


def get_sub_array(array,i,j,width,height):
    sub_array=[]
    for n in range(i,i+height):
        sub_array.append(array[n][j:j+width])
    return sub_array

def compare(arr1,arr2):
    for i in range(len(arr1)):
        for j in range(len(arr1[0])):
            if arr1[i][j]!=arr2[i][j]:
                return False
    return True


def is_sub_array(hay,needle):
    hay_width=len(hay[0])
    hay_height=len(hay)
    needle_width=len(needle[0])
    needle_height=len(needle)

    for i in range(hay_height-needle_height+1):
        for j in range(hay_width-needle_width+1):
            if hay[i][j]==needle[0][0]:
                if compare(
                    get_sub_array(hay,i,j,needle_width,needle_height),
                    needle
                    ):
                    return True
    return False

print(is_sub_array(hay,needle))

输出：

True

- Liju