Apa beberapa hasil yang diketahui untuk menemukan subarray n-dimensi yang tepat di dalam array n-dimensi?
Dalam 1D, itu hanya masalah pencocokan string, KMP melakukannya dalam waktu linier.
Dalam 2D, makalah ini menunjukkan dapat dilakukan dalam waktu linier dengan sedikit ruang ekstra.
Bisakah masalah ini diselesaikan dalam kasus terburuk linear waktu untuk dimensi tetap?
Anda dapat memecahkan masalah dalam jumlah tetap dimensi dengan memperluas solusi asli waktu linear dari Bird dari 1977 http://www.sciencedirect.com/science/article/pii/0020019077900175 (berlangganan diperlukan dengan sedih).
Gagasan umum (dalam 2D) adalah pada langkah 1 untuk membangun otomat Aho-Corasick dari baris-baris dari pola 2D dan kemudian memberi makan dalam baris-baris teks 2D satu per satu. Anda kemudian akan menemukan semua posisi yang cocok dengan baris pola dalam teks. Untuk menyelesaikan Anda sekarang hanya perlu melakukan pencarian 1D untuk (label) baris pola dalam urutan yang benar di kolom pada output dari langkah 1, menggunakan KMP katakan. Ini semua membutuhkan waktu linier.
Dengan menggunakan metode yang sama Anda dapat mengurangi dari dimensi apa pun masalah pencocokan tepat ke masalah dimensi d-1. Dengan cara ini Anda mendapatkan solusi waktu linier untuk dimensi tetap apa pun d.
Dimungkinkan untuk menyelesaikannya dalam waktu linier hampir (faktor polylog) dengan menggunakan teknik FFT. Anda dapat melihat di kertas: http://www.cs.tau.ac.il/~klim/papers/CEPR08.pdf di mana kami menggunakan teknik FFT untuk pencocokan pola satu dimensi. Jika Anda ingin menyelesaikan pencocokan pola multidimensi, Anda hanya perlu menggunakan FFT dimensi tinggi.