# Sparse bit string pattern matching

Suppose there are two strings of bits. Let's call them the needle (n) and the haystack (h).

We'll say that the needle matches the haystack at position i iff, for all j, h[i + j] -> n[j], where -> is the material implication. In other words, if a bit is cleared in the needle, it must also be cleared in the haystack, if there is to be a match.

The needle and the haystack are long, but sparse, strings of bits. The needle is given as the set of indices, at which it has zeros/cleared bits. All other bits in the needle are assumed to be ones/set - pose no constraints. The haystack is given as the set of indices, at which it has ones/set bits. All other bits in the haystack are assumed to be zeros/cleared - satisfy all constraints.

Is there any position, at which the needle matches the haystack?

• Where are you stuck on this? An algo seems pretty straightforward to create here
– EnEm
Commented Jun 17 at 21:31
• What's the best algorithm you've found so far? What is its running time? What is the context where you have encountered this problem? Can you credit the original source?
– D.W.
Commented Jun 18 at 1:55
• Should the strategy be different for a single match as opposed to matching many needles to the same haystack? Commented Jun 18 at 5:48