in reply to Re^3: [OT] The interesting problem of comparing bit-strings.
in thread [OT] The interesting problem of comparing bit-strings.

DFA space requirement and construction are both O(m*s) where m is needle length and s the alphabet size. Search is O(n) (linear to text size). In practice, one would handle say 8 bits (a byte) at a time. Even then, the space requirement hardly matters with small patterns..

  • Comment on Re^4: [OT] The interesting problem of comparing bit-strings.

Replies are listed 'Best First'.
Re^5: [OT] The interesting problem of comparing bit-strings.
by salva (Canon) on Mar 24, 2015 at 21:11 UTC
    The think is that O(m*s) can actually be huge!

    For a 256 alphabet and supposing that a pointer per entry is enough, it results in 1KB per needly byte. Three orders of magnitude bigger than the needle size.

    Admittedly, that is a worst case scenario as in most cases, the transition tables collapse into just a few exits per state and can be represented in more efficient ways. But I don't know if the OP case fits into that "most cases".

[reply]
[d/l]
[reply]

In Section Seekers of Perl Wisdom