O(m * n) lookaround

[rpjohnst]

A 2024 POPL paper proposed a new NFA-based algorithm for matching regular expressions with arbitrary lookaround in O(m * n) time, without the previously-required exponential blowup in automaton size or matching time: https://dl.acm.org/doi/10.1145/3632934

Its main limitation is that, for regular expressions with both lookahead and lookbehind, it no longer supports streaming, because each form of lookaround involves a pass from its associated direction, and an O(n) buffer to hold the results. (With only one or the other, everything can be done in one pass and without the buffer.)

They show some pretty competitive benchmarks with PCRE2 and Java's regex engine as well.

I don't personally have a way to judge how worthwhile this would be, but I thought you would be interested to hear about it in any case!

[shilangyu]

An implementation of look-behinds with a streaming algorithm has been implemented and opened as a PR: #1266