Algorithm to check if a multidimensional array contains another?

Question

Say I have two multidimensional arrays of equal depth, say:

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

and

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

What sort of algorithm can I follow to determine if the latter is a contiguous subarray of the former?

For example, with the above example, it is:

And also with this pair of 3d arrays:

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

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

Another way of interpreting this is that by removing the first or last item from a dimension of the first array repeatedly, you will eventually get the target array.

Answer 1

The Rabin-Karp string search algorithm can be extended to multiple dimensions to solve this problem.

Lets say your pattern array is M rows by N columns:

1. Using any rolling hash function, like a polynomial hash, first replace every column of your pattern array with the hash of the column, reducing it to 1 dimension. Then hash the remaining row. This will be your pattern hash.

2. Now use the rolling hash in your target array to replace all values in rows >= M by the hash of those values with the M-1 values above them.

3. Then, similarly replace all remaining values in columns >= N-1 with the hash of those values and the N-1 values to the left.

4. Finally, find any instances of the pattern hash in the resulting matrix. When you find one, compare with your pattern array to see if it's a real match.

This algorithm extends to as many dimensions as you like and, like simple Rabin-Karp, it takes O(N) expected time if the number of dimensions is constant.