Quels sont les résultats connus pour trouver un sous-tableau exact à n dimensions dans un tableau à n dimensions?
Dans 1D, c'est juste un problème de correspondance de chaînes, KMP le fait en temps linéaire.
En 2D, cet article a montré que cela peut être fait en temps linéaire avec peu d'espace supplémentaire.
Ce problème peut-il être résolu dans le pire des cas en temps linéaire pour n'importe quelle dimension fixe?
Vous pouvez résoudre le problème dans un nombre fixe de dimensions en étendant la solution originale à temps linéaire de Bird de 1977 http://www.sciencedirect.com/science/article/pii/0020019077900175 (abonnement nécessaire malheureusement).
L'idée générale (en 2D) est à l'étape 1 de construire un automate Aho-Corasick des rangées du motif 2D puis d'alimenter les rangées du texte 2D une par une. Vous trouverez alors toutes les positions que les lignes du motif correspondent dans le texte. Pour terminer, il vous suffit maintenant de faire une recherche 1D pour les (étiquettes de) les lignes du motif dans le bon ordre dans une colonne dans la sortie de l'étape 1, en utilisant KMP say. Tout cela prend du temps linéaire.
En utilisant la même méthode, vous pouvez réduire de n'importe quel problème de correspondance exacte de dimension d à un problème de dimension d-1. De cette façon, vous obtenez une solution de temps linéaire pour toute dimension fixe d.
Il est possible de le résoudre en un temps presque (jusqu'à un facteur polylog) linéaire en utilisant des techniques FFT. Vous pouvez consulter le document: http://www.cs.tau.ac.il/~klim/papers/CEPR08.pdf où nous utilisons des techniques FFT pour l'appariement de motifs unidimensionnels. Si vous souhaitez résoudre la correspondance de motifs multidimensionnels, il vous suffit d'utiliser la FFT de haute dimension.