は、大きなバイナリ行列の小さいバイナリ行列の出現を数えます。

Question

2つのバイナリ行列m1とm2が与えられ、m2はm1と比較して（等しい次元で）大きさが同じか大きいことが保証されます。 m2内のm1の外観を数えるためにC++で関数を記述します。例：

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

平方メートルで2回登場M1、その後、機能が返す整数2.

誰もが効率的にこの問題を解決するためにビット操作ベースの方法を使用することはできますか？

Answer 1

バイナリパターンをランレングスエンコーディングで表現すると、問題は圧縮された表現で一致する通常の文字列に変わり、ビットの操作は必要ありません。

次に、Boyer-Mooreのような標準的なアルゴリズムに頼ることができます。不一致が見つかった場合は、すべての行で見つかったものの中で最も長いシフトを使用できます。