Correspondência de expressão regular de tempo totalmente linear

Existe um algoritmo para verificar se uma expressão regular de tamanho corresponde a uma string de tamanho , assumindo um alfabeto de tamanho fixo, se isso importa?$O(n+m)$$n$$m$

O algoritmo NFA padrão é pior caso de . Groz et al. obtenha tempo linear para uma variedade de classes de expressão regular, mas não todas. Existem melhores resultados?$O(nm)$

Groz, B., Maneth, S., & Staworko, S. (2012, maio). Expressões regulares determinísticas em tempo linear.

Groz et al. explicitamente estado que o melhor algoritmo conhecido por expressões regulares gerais (a partir de 2012) é , devido à Bille e Thorup 2009, doi: 10,1007 / 978-3-642-02927-1_16 ( pré-impressão ).$O(nm(\log\log n)/(\log n)^{3/2}+n+m)$

$O(n+m)$$O(m+n)$