1
Finding all regex matches has always been O(n²)
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 the iteration loop.
ian erik varatalu
phd student at taltech, working on automata theory, algorithms, fast search engines and solvers.
- Popular posts
- 3
- Total points
- 626
- HN comments
- 198
- Rank
- #3,943 personal
Visit iev.ee → RSS feedOn Hacker News Mar 2026 – Mar 2026
Software Engineering 3Systems & Performance 1Math & Algorithms 1Programming Languages 1
2
RE#: how we built the fastest regex engine in F#
around a year ago, we built a regex engine in F# that not only outperformed the ones in dotnet, but went above and beyond competing with every other industrial regex engine on a large set of industry-standard benchmarks. it also supports the full set of boolean operators (union, intersection, complement) and even a…
3
Gzip decompression in 250 lines of Rust
i wanted to have a deeper grasp of how compression works, so i wrote a gzip decompressor from scratch. the result is about 250 lines of rust that can decompress gzip from a file or stdin.