在大二进制矩阵中计算小二进制矩阵的外观

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这样的标准算法，当发现不匹配时，您可以使用所有行中找到的最长偏移。