Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
