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