zählen das Auftreten einer kleinen binären Matrix in einer großen binären Matrix

Question

gegeben zwei Binärmatrizen m1 und m2, m2 ist garantiert, eine größere oder gleiche Größe (in beiden Dimensionen) im Vergleich zu m1 zu haben. Schreibe eine Funktion in C++, um das Aussehen von m1 in m2 zu zählen. z.B.

m1 = [1 1; 1 1], m2 = [1 1 0 0; 1 1 0 0; 0 0 1 1 0 0 1 1]

dann m1 in m2 2 Mal erschien, sollte die Funktion zurückgeben integer 2.

Kann jemand eine wenig Manipulation basierte Methode, um dieses Problem effizient zu lösen?

Answer 1

Wenn Sie Ihre binären Muster mit Lauflängencodierung darstellen, wird das Problem zu einer gewöhnlichen Zeichenkette, die einer entspricht, auf einer komprimierten Darstellung, und es ist kein bisschen fiedeln erforderlich.

Dann können Sie zu einem Standardalgorithmus wie Boyer-Moore greifen, und wenn eine Abweichung gefunden wird, können Sie die längste Verschiebung zwischen denen in allen Zeilen gefunden.