Thu, 21 Aug 2008 15:22:31 BST CiteULike: arthit's Gonnet http://www.citeulike.org/user/arthit/author/Gonnet CiteULike.org en-gb Copyright © 2004-2008 citeulike.org http://www.citeulike.org/user/arthit/article/1154354 <i>Journal of the ACM, Vol. 43, No. 6. (1996), pp. 915-936.</i><br /><br />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... Fast text searching for regular expressions or automaton searching on tries Richardo Gaston Gonnet Journal of the ACM, Vol. 43, No. 6. (1996), pp. 915-936. 2007-03-11T19:34:51-00:00 1996 Journal of the ACM 43 6 915 936 matching regular-expression search string text