finding all regex matches has always been O(n²). even in the engines built to prevent it

every regex engine that promises linear time breaks that promise the moment you ask for all matches. the problem has been there since the 70s, hiding in plain sight.
— by ian erik varatalu

🤔 https://iev.ee/blog/the-quadratic-problem-nobody-fixed/

#regex #problem #coding #70s #blogpost #find #blog #liner #lineartime #time