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.
No takes yet. Share an insight, caveat, or question.
Baeza‐Yates et al. (1996) studied this question.
Synapse has enriched 2 closely related papers on similar clinical questions. Consider them for comparative context: