Jakie są znane wyniki znalezienia dokładnej n-wymiarowej podtablicy wewnątrz n-wymiarowej tablicy?
W 1D jest to tylko problem dopasowania łańcucha, KMP robi to w czasie liniowym.
W 2D ten dokument pokazał, że można to zrobić w czasie liniowym z niewielką dodatkową przestrzenią.
Czy ten problem można rozwiązać w najgorszym przypadku liniowym dla dowolnego ustalonego wymiaru?
Możesz rozwiązać problem w ustalonej liczbie wymiarów, przedłużając oryginalne rozwiązanie liniowe Bird z 1977 r. Http://www.sciencedirect.com/science/article/pii/0020019077900175 (niestety wymagana subskrypcja).
Ogólną ideą (w 2D) jest krok 1, aby zbudować automat Aho-Corasicka wierszy wzoru 2D, a następnie wprowadzać kolejno wiersze tekstu 2D. Następnie znajdziesz wszystkie pozycje, które wiersze wzoru pasują do tekstu. Aby zakończyć, wystarczy teraz przeprowadzić wyszukiwanie 1D (etykiet) wierszy wzoru we właściwej kolejności w kolumnie na wyjściu z kroku 1, używając KMP say. Wszystko to zajmuje czas liniowy.
Za pomocą tej samej metody można zredukować problem dokładnego dopasowania wymiaru d do problemu wymiaru d-1. W ten sposób otrzymujesz liniowe rozwiązanie czasowe dla dowolnego stałego wymiaru d.
Możliwe jest rozwiązanie tego w prawie (współczynniku up to polilog) liniowym czasie przy użyciu technik FFT. Możesz zajrzeć na papier: http://www.cs.tau.ac.il/~klim/papers/CEPR08.pdf, gdzie używamy technik FFT do dopasowywania jednowymiarowych wzorów. Jeśli chcesz rozwiązać wielowymiarowe dopasowywanie wzorów, wystarczy użyć wielowymiarowego FFT.