Ah, I see -- thanks! The author of the article works for google, and he wrote software for them that would accept regexp from random users on the web, so he wanted something that would always take linear time. (OTOH, seems like he could simply use any random regexp engine and put a time limit on how long it was allowed to tun.)