Fast text searching for regular expressions or automaton searching on tries
Ricardo A. Baeza-Yates, Gastón H. Gonnet · Journal of the ACM · 1996
We present algorithms for efficient searching of regular expressions on preprocessed text, using a Patricia tree as a logical model for the index. We obtain searching algorithms that run in logarithmic expected time in the size of the text for a wide subclass of regular expressions, and in sublinear expected time for any regular expression. This is the first such algorithm to be found with this complexity.