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.