Каковы некоторые известные результаты для нахождения точного n-мерного подмассива внутри n-мерного массива?
В 1D это просто проблема соответствия строк, KMP делает это за линейное время.
В 2D эта статья показала, что это можно сделать за линейное время с небольшим дополнительным пространством.
Можно ли решить эту проблему в наихудшем случае с линейным временем для любого фиксированного размера?
Вы можете решить проблему в фиксированном количестве измерений, расширив оригинальное решение Bird с линейным временем с 1977 г. http://www.sciencedirect.com/science/article/pii/0020019077900175 (подписка нужна, к сожалению).
Общая идея (в 2D) состоит в том, чтобы на шаге 1 построить автомат Aho-Corasick из строк 2D-шаблона, а затем подавать в строки 2D-текста одну за другой. Затем вы найдете все позиции, которым соответствуют строки шаблона в тексте. Для завершения вам теперь нужно только выполнить одномерный поиск (меток) строк шаблона в правильном порядке в столбце в выходных данных шага 1, используя команду KMP. Все это занимает линейное время.
Используя тот же метод, вы можете превратить любую задачу точного соответствия измерения d в задачу измерения d-1. Таким образом, вы получите линейное временное решение для любого фиксированного размера d.
Это можно решить за почти (до множителя) линейное время, используя методы БПФ. Вы можете посмотреть на бумаге: http://www.cs.tau.ac.il/~klim/papers/CEPR08.pdf, где мы используем методы БПФ для сопоставления одномерного образца. Если вы хотите решить сопоставление многомерного шаблона, вам просто нужно использовать многомерное БПФ.