FINDING ALL REGEX MATCHES HAS ALWAYS BEEN O(N²). EVEN IN THE ENGINES BUILT TO PREVENT IT

Summary from the TLDR Dev newsletter

Most regex engines, despite advertising linear time for single matches, suffer from a quadratic (O(n²)) performance problem when finding all matches. RE# is a novel regex engine designed to resolve this by using a two-pass algorithm, a reverse and a forward DFA, to efficiently identify all leftmost-longest matches in guaranteed linear time. It has a "hardened mode" for linear performance against adversarial inputs, and its default mode is also quite fast.