20

What are some known results for finding an exact n-dimensional subarray inside a n-dimensional array?

In 1D, it is just a string matching problem, KMP does it in linear time.

In 2D, this paper shown it can be done in linear time with little extra space.

Can this problem be solved in linear time worst case for any fixed dimension?

Chao Xu
  • 4,399
  • 23
  • 32

2 Answers2

13

You can solve the problem in a fixed number of dimensions by extending the linear time original solution of Bird from 1977 http://www.sciencedirect.com/science/article/pii/0020019077900175 (subscription needed sadly).

The general idea (in 2D) is in step 1 to build an Aho-Corasick automaton of the rows of the 2D pattern and then feed in the rows of the 2D text one by one. You will then find all the positions that the pattern rows match in the text. To finish you now only need to do a 1D search for the (labels of) the rows of the pattern in the right order in a column in the output of step 1, using KMP say. This all takes linear time.

Using the same method you can reduce from any dimension d exact matching problem to a dimension d-1 problem. In this way you get a linear time solution for any fixed dimension d.

Simd
  • 3,902
  • 20
  • 49
9

It is possible to solve it in almost(upto polylog factor) linear time using FFT techniques. You can look on the paper: http://www.cs.tau.ac.il/~klim/papers/CEPR08.pdf where we use FFT techniques for one dimensional pattern matching. If you want to solve multidimensional pattern matching you just need to use high dimensional FFT.

Klim
  • 903
  • 4
  • 16
  • Given the paper is from 2008, I assume linear time algorithms are not yet known. – Chao Xu Oct 02 '11 at 05:25
  • I gave it only as an example of technique could be used to solve your problem. Advantage of this approach that this allow you also to solve the problem with mismatches and don't cares. But as for exact one dimentional pattern matching exists linear time alg. so may be it is known for multi-dimensional. – Klim Oct 02 '11 at 08:11
  • 1
    I think the basic result on pattern matching with wildcards is from Fischer and Paterson 1974 and then continuously tweaked and simplified until http://www.cs.bris.ac.uk/Publications/pub_master.jsp?id=2000602 (apologies for the self citation). However, it may be slight overkill for the problem the OP asked given the older exact matching method I mention below. – Simd Oct 02 '11 at 08:14