<p>It is possible to solve it in almost(upto polylog factor) linear time using FFT techniques. You can look on the paper: 
<a href="http://www.cs.tau.ac.il/~klim/papers/CEPR08.pdf" rel="nofollow">http://www.cs.tau.ac.il/~klim/papers/CEPR08.pdf</a> 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.   </p>

CC BY-SA 3.0
2011-10-02T05:25:22.020Z
Given the paper is from 2008, I assume linear time algorithms are not yet known.
Chao Xu
CC BY-SA 3.0
2011-10-02T08:11:50.383Z
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
CC BY-SA 3.0
2011-10-02T08:14:11.067Z
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
CC BY-SA 3.0
2011-10-01T18:13:02.653Z
2011-10-01T18:13:02.653Z
Klim
<p>You can solve the problem in a fixed number of dimensions by extending the linear time original solution of Bird from 1977 <a href="http://www.sciencedirect.com/science/article/pii/0020019077900175">http://www.sciencedirect.com/science/article/pii/0020019077900175</a> (subscription needed sadly).</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2011-10-02T06:19:56.433Z
2011-10-02T08:15:27.647Z
2011-10-02T08:15:27.647Z
Simd
<p>What are some known results for finding an exact n-dimensional subarray inside a n-dimensional array?</p>

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

<p>In 2D, <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.44.6976">this paper</a> shown it can be done in linear time with little extra space.  </p>

<p>Can this problem be solved in linear time worst case for any fixed dimension?</p>

<ds.algorithms><reference-request><string-matching>
n-dimensional pattern matching
Chao Xu
# n-dimensional pattern matching

(Asked by: username_0 on 2011-10-01)

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](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.44.6976) 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?

**Tags:** ds.algorithms, reference-request, string-matching

---

## 2 answers

### Answer by username_2 on 2011-10-02. Score: 13 | Accepted answer

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.


---

### Answer by username_1 on 2011-10-01. Score: 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.

> **Comments:**
> **username_0**: Given the paper is from 2008, I assume linear time algorithms are not yet known.  
> **username_1**: 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.  
> **username_2**: 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.  

---

