Coincidencia de expresiones regulares de tiempo completamente lineal

8

¿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?O(norte+metro)nortemetro

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?O(nortemetro)

Groz, B., Maneth, S. y Staworko, S. (2012, mayo). Expresiones regulares deterministas en tiempo lineal.

Geoffrey Irving
fuente

Respuestas:

5

Groz y col. explícitamente estado que el mejor algoritmo conocido para las expresiones regulares generales (a partir de 2012) es , debido a Bille y Thorup 2009, doi: 10.1007 / 978-3-642-02927-1_16 ( preimpresión ).O(nortemetro(Iniciar sesiónIniciar sesiónnorte)/ /(Iniciar sesiónnorte)3/ /2+norte+metro)

O(norte+metro)O(metro+norte)

András Salamon
fuente