¿Existe un algoritmo para verificar si una expresión regular de tamaño n coincide con una cadena de tamaño m , suponiendo un alfabeto de tamaño fijo si eso importa?
El algoritmo estándar de NFA es peor de los casos. Groz y col. lograr tiempo lineal para una variedad de clases de expresiones regulares, pero no todas. ¿Hay mejores resultados?
Groz, B., Maneth, S. y Staworko, S. (2012, mayo). Expresiones regulares deterministas en tiempo lineal.
regular-expressions
parsing
Geoffrey Irving
fuente
fuente