Check out Shift-Or: used in agrep, and another example of a very clever algorithm. Rather than translating a non-deterministic finite state automata to a deterministic one, it uses the boolean operations of the hardware to simulate the NFA directly. Result: linear time regexp for patterns that have less than the bit-length of a machine's registers. I.e., 32 bytes on x86, 64 bytes on x86_64, etc.
Comments
http://en.wikipedia.org/wiki/Shift-or
Check out Shift-Or: used in agrep, and another example of a very clever algorithm. Rather than translating a non-deterministic finite state automata to a deterministic one, it uses the boolean operations of the hardware to simulate the NFA directly. Result: linear time regexp for patterns that have less than the bit-length of a machine's registers. I.e., 32 bytes on x86, 64 bytes on x86_64, etc.