Faster Regular Expression Matching via Two-Dimensional Tabulation

Regular expression matching asks whether a string of length n belongs to the language described by a regular expression of length m. We give an algorithm that solves this problem in linear space and O(nm log log n/log² n + n + m) time. This improves the leading term of the previous best worst-case constant-alphabet time bound by a factor of √log n. The key new technique is a two-dimensional tabulation specialized to the regular expression.