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?

  • 1
    $\begingroup$ Where are you stuck on this? An algo seems pretty straightforward to create here $\endgroup$
    – EnEm
    Commented Jun 17 at 21:31
  • 2
    $\begingroup$ 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? $\endgroup$
    – D.W.
    Commented Jun 18 at 1:55
  • 1
    $\begingroup$ Should the strategy be different for a single match as opposed to matching many needles to the same haystack? $\endgroup$
    – greybeard
    Commented Jun 18 at 5:48


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.