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

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".

Replies are listed 'Best First'.
Re^6: [OT] The interesting problem of comparing bit-strings.
by Anonymous Monk on Mar 24, 2015 at 21:34 UTC