Quais são alguns resultados conhecidos para encontrar um subarray n-dimensional exato dentro de uma matriz n-dimensional?
Em 1D, é apenas um problema de correspondência de cadeias, o KMP faz isso em tempo linear.
Em 2D, este artigo mostrou que isso pode ser feito em tempo linear com pouco espaço extra.
Esse problema pode ser resolvido no pior caso de tempo linear para qualquer dimensão fixa?
Você pode resolver o problema em um número fixo de dimensões, estendendo a solução original em tempo linear da Bird de 1977 http://www.sciencedirect.com/science/article/pii/0020019077900175 (assinatura necessária infelizmente).
A idéia geral (em 2D) está na etapa 1 para criar um autômato Aho-Corasick das linhas do padrão 2D e depois alimentar as linhas do texto 2D, uma a uma. Você encontrará todas as posições correspondentes às linhas do padrão no texto. Para finalizar, agora você só precisa fazer uma pesquisa 1D pelas (etiquetas) linhas do padrão na ordem correta em uma coluna na saída da etapa 1, usando o KMP say. Tudo isso leva tempo linear.
Usando o mesmo método, você pode reduzir de qualquer problema de correspondência exata da dimensão d para um problema da dimensão d-1. Dessa forma, você obtém uma solução de tempo linear para qualquer dimensão fixa d.
É possível resolvê-lo em tempo quase linear (até o fator polilogênico) usando técnicas de FFT. Você pode ver o artigo: http://www.cs.tau.ac.il/~klim/papers/CEPR08.pdf, onde usamos técnicas de FFT para a correspondência de padrões unidimensionais. Se você deseja resolver a correspondência de padrões multidimensionais, basta usar a FFT de alta dimensão.