在大二進制矩陣中計算小二進制矩陣的外觀

Question

給定兩個二進制矩陣m1和m2，與m1相比，m2保證具有更大或相等的尺寸（在兩個維度上）。用C++編寫一個函數來計算m2內m1的外觀。 例如

m1 = [1 1; 11]，m2 = [1 0 0; 1 1 0 0; 0 0 1 1 0 0 1 1]

然後M1中平方米出現2次，則該函數將返回整數2.

任何人都可以使用一個基於位操作方法有效地解決這個問題？

Answer 1

如果使用運行長度編碼來表示二進制模式，則問題將轉換爲與壓縮表示匹配的一個普通字符串，並且不需要任何操作。

然後您可以使用Boyer-Moore這樣的標準算法，當發現不匹配時，您可以使用所有行中找到的最長偏移。