You know, someone ought to write a book about that (time increasing with regex complexity). :-)