Is there an $O(n+m)$ algorithm to check whether a size $n$ regular expression matches a size $m$ string, assuming a fixed size alphabet if that matters?

The standard NFA algorithm is $O(nm)$ worst case. Groz et al. achieve linear time for a variety of regular expression classes, but not all. Are there any better results?

Groz, B., Maneth, S., & Staworko, S. (2012, May). Deterministic regular expressions in linear time.


Groz et al. explicitly state that the best known algorithm for general regular expressions (as of 2012) is $O(nm(\log\log n)/(\log n)^{3/2}+n+m)$, due to Bille and Thorup 2009, doi:10.1007/978-3-642-02927-1_16 (preprint).

For a fixed size alphabet, Sebastian Maneth pointed out to me that $O(n+m)$ is possible for deterministic regular expressions by constructing the Glushkov DFA: each position in the regular expression is one state, and the transitions are determined by the bounded set of symbols that may appear before moving to a position. However, without fixing the alphabet size, it still holds that "finding a time $O(m+n)$ algorithm remains an open problem" even in the deterministic case.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.