Finding all regex matches has always been O(n²)
La plupart des moteurs regex garantissent le temps linéaire pour une seule correspondance, mais l'obtention de toutes les correspondances peut exposer à une complexité quadratique en pratique. Des moteurs comme RE2, le regexp de Go et le crate regex de Rust offrent un temps linéaire pour une correspondance unique, mais l'itération sur toutes les correspondances annule cette garantie et peut atteindre O(m · n²). RE# propose une approche en deux passes qui identifie d'abord les débuts possibles puis résout les fins, afin de rapporter toutes les correspondances sans réanalyser indéfiniment le même segment. Pour aller plus loin, RE# introduit un mode hardened qui remplace la passe directe par une analyse en O(n · S) afin de résoudre toutes les terminaisons en une seule passe et garantir une complexité linéaire en toutes circonstances. Le texte compare aussi à Aho-Corasick, évoque des limites comme l'absence de captures et de quantificateurs paresseux, et indique que l'outil est encore en développement malgré des gains significatifs sur certains jeux de tests.