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

问：

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

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

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

算法多维数组语言无关

使用任何滚动哈希函数（如多项式哈希），首先将模式数组的每一列替换为列的哈希值，将其减少到 1 维。然后对剩余的行进行哈希处理。这将是您的模式哈希。
现在，使用目标数组中的滚动哈希值将行 >= M 中的所有值替换为这些值的哈希值，并在其上方使用 M-1 值。
然后，同样地将列 >= N-1 中的所有剩余值替换为这些值的哈希值和左侧的 N-1 值。
最后，在生成的矩阵中查找模式哈希的任何实例。当你找到一个时，与你的模式数组进行比较，看看它是否是真正的匹配。

该算法可扩展到任意数量的维度，并且与简单的 Rabin-Karp 一样，如果维度数保持不变，则需要 O（N） 的预期时间。

0赞 Liju 7/31/2022 #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

上一个：给定一个未排序的二进制数组，计数 1 的数量，其中只允许检查整个子数组是否全部为零

下一个：两个反向排序数组的复杂度

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

Algorithm to check if a multidimensional array contains another?

评论