Puede resolver el problema en un número fijo de dimensiones extendiendo la solución original de tiempo lineal de Bird desde 1977 http://www.sciencedirect.com/science/article/pii/0020019077900175 (lamentablemente, se necesita una suscripción).
La idea general (en 2D) está en el paso 1 para construir un autómata Aho-Corasick de las filas del patrón 2D y luego alimentar las filas del texto 2D una por una. Luego encontrará todas las posiciones que coinciden con las filas del patrón en el texto. Para terminar, ahora solo necesita hacer una búsqueda en 1D de las (etiquetas de) las filas del patrón en el orden correcto en una columna en la salida del paso 1, usando KMP say. Todo esto lleva tiempo lineal.
Con el mismo método, puede reducir el problema de coincidencia exacta de cualquier dimensión d a un problema de dimensión d-1. De esta manera obtienes una solución de tiempo lineal para cualquier dimensión fija d.