Bitap: my favorite string matching algorithm

This was a great read, thanks for writing it! I now feel the need to implement this in my toy regex engine.

I think the NFA picture is the simplest and most illuminating for this class of algorithms. It's easy to write down an NFA for substring matching a given string. When you number that NFA's states sequentially and represent a set of states as a bitvector, the NFA transition function becomes a masked shift operation on the bitvector (versus simulating the NFA with something general like Thompson's algorithm).

Navarro's Flexible Pattern Matching in Strings covers many bit-parallel algorithms in depth, if that sounds interesting.