n-dimensional pattern matching 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?
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.