정규식(Regex)에서 모든 매치 찾기 문제는 기존의 선형 시간 복잡도를 보장하는 엔진들(RE2, Go, Rust 등)에서도 실제로는 모든 매치를 요청할 때 최악의 경우 이차 시간 복잡도(O(n²))​가 발생한다는 점을 지적합니다. 이는 대부분의 연구가 단일 매치 문제에 집중하고, 모든 매치를 찾는 과정에서 발생하는 비용을 간과한 결과입니다.

저자는 **RE#**라는 새로운 정규식 엔진을 소개하며, 이 엔진은 입력을 두 번의 패스로 처리하여 모든 매치를 선형 시간 내에 찾으면서도 기존의 leftmost-longest(좌측 최장) 매치 의미론을 유지합니다. 또한, RE#는 hardened 모드를 통해 악의적 패턴과 입력에서도 선형 성능을 보장하며, 이는 기존 엔진들이 겪는 이차 시간 복잡도 문제를 극복한 혁신적인 접근입니다.

다만, RE#는 캡처 그룹, 게으른 수량자(lazy quantifier)를 지원하지 않고, 바이트 단위 API를 사용하는 등 아키텍처적 한계가 존재하지만, 복잡한 패턴에서도 일관된 의미론과 성능을 중시하는 용도에 적합합니다. 마지막으로, 스트리밍 처리에 대해서는 leftmost-longest 의미론과 무한 스트림이 본질적으로 충돌하기 때문에, 라인 단위와 같은 명확한 경계가 있을 때만 실용적임을 설명합니다.