Mikhail Lakunin

Automaton Searching on Tries

Abstract

Above there were considered a lot of algorithms that allow us to search for a pattern in a string and a few powerful methods to give asymptotic estimations of such algorithms. There is an extension of such algorithms, not for one pattern but for a regular expression. The algorithms that are to be reviewed there run on the preprocessed text (we use Patricia tree) and are of logarithmic expected time of the size of the text for the stricted class of regular expressions and in a sublinear expected time for all regular expressions.
It's the first such algorithm to be found with this complexity.
The main purpose of the text is to give understanding of what's going on, and therefore some of the technicals could be omitted. For the precise explanation the reader is referred to the original paper.