Ken Thompson: Regular Expression Search Algorithm [pdf]

i have actually been implementing this algorithm in c using a VM based approach. there are analyses of these techniques that are a little less dense than whats in the paper here: http://swtch.com/~rsc/regexp/regexp1.html and http://swtch.com/~rsc/regexp/regexp2.html

the really amazing thing about this algorithm is stated in the third to last paragraph where he explains that strict bounds can be put on the size of the two lists that are used to manage the runtime state. this turns the algorithm from a potentially exponential runtime to O(MN) where M is the size of the regex and N is the length of the string being matched