Fast text searching for regular expressions or automaton searching on tries

@article{citeulike:1154354, abstract = {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 which 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. 1 Introduction Pattern matching and text searching are very important components of...}, author = {Richardo and Gonnet, Gaston H. }, citeulike-article-id = {1154354}, journal = {Journal of the ACM}, keywords = {matching, regular-expression, search, string, text}, number = {6}, pages = {915--936}, posted-at = {2007-03-11 19:35:20}, priority = {2}, title = {Fast text searching for regular expressions or automaton searching on tries}, url = {http://citeseer.ist.psu.edu/110994.html}, volume = {43}, year = {1996} }

TY - JOUR ID - citeulike:1154354 L3 - citeulike-article-id:1154354 TI - Fast text searching for regular expressions or automaton searching on tries JF - Journal of the ACM VL - 43 IS - 6 SP - 915 EP - 936 N2 - 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 which 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. 1 Introduction Pattern matching and text searching are very important components of... KW - matching KW - regular-expression KW - search KW - string KW - text AU - Richardo AU - Gonnet, Gaston PY - 1996/// UR - http://citeseer.ist.psu.edu/110994.html ER -