A Four Russians algorithm for regular expression pattern matching
Gene Myers · Journal of the ACM · 1992
Given a regular expression R of length P and a word A of length N , the membership problem is to determine if A is in the language denoted by R . An O ( PN /lg N ) time algorithm is presented that is based on a lg N speedup of the standard O ( PN ) time simulation of R 's nonderministic finite automaton on A using a combination of the node-listing and “Four-Russians” paradigms. This result places a new worst-case upper bound on regular expression pattern matching. Moreover, in practice the method provides an implementation that is faster than existing software for small regular expressions.