Encontrar todas as correspondências de regex sempre foi O(n²), mesmo nos motores projetados para evitá-lo

A maioria dos motores de regex, apesar de anunciarem tempo linear para correspondências únicas, sofre de um problema de desempenho quadrático (O(n²)) ao encontrar todas as correspondências. O RE# é um motor de regex inovador projetado para resolver isso, utilizando um algoritmo de dois passos, combinando um DFA reverso e um direto, para identificar eficientemente todas as correspondências à esquerda e mais longas em tempo linear garantido. Ele possui um "modo reforçado" para desempenho linear contra entradas adversárias, e seu modo padrão também é bastante rápido.