<p>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:<a href="http://dx.doi.org/10.1007/978-3-642-02927-1_16">10.1007/978-3-642-02927-1_16</a> (<a href="http://www2.compute.dtu.dk/~phbi/files/publications/2009fremC.pdf">preprint</a>).</p>

<p>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.</p>

CC BY-SA 3.0
2015-08-10T19:30:01.433Z
2015-08-10T19:30:01.433Z
András Salamon
<p>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?</p>

<p>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?</p>

<p>Groz, B., Maneth, S., &amp; Staworko, S. (2012, May). Deterministic regular expressions in linear time.</p>

<regular-expressions><parsing>
Fully linear time regular expression matching
Geoffrey Irving
# Fully linear time regular expression matching

(Asked by: username_0 on 2015-08-07)

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.

**Tags:** regular-expressions, parsing

---

## 1 answers

### Answer by username_1 on 2015-08-10. Score: 6 | Accepted answer

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](http://dx.doi.org/10.1007/978-3-642-02927-1_16) ([preprint](http://www2.compute.dtu.dk/~phbi/files/publications/2009fremC.pdf)).

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.


---

