# Efficient Matching with Memoization for Regexes with Look-around and Atomic Grouping (Extended Version)

arXiv: https://arxiv.org/abs/2401.12639 · HTML: https://mlsanity.com/paper/2401.12639/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Jan 2024.

## Built on by (most cited first, 2 of 2)

- [Lost in Translation? Converting RegExes for Log Parsing into Dynatrace Pattern Language](https://mlsanity.com/paper/2506.19539/) (2025)
- [On the Complexity of the Matching Problem of Regular Expressions with Backreferences](https://mlsanity.com/paper/2605.07289/) (2026)

## Abstract (arXiv)

Regular expression (regex) matching is fundamental in many applications, especially in web services. However, matching by backtracking -- preferred by most real-world implementations for its practical performance and backward compatibility -- can suffer from so-called catastrophic backtracking, which makes the number of backtracking super-linear and leads to the well-known ReDoS vulnerability. Inspired by a recent algorithm by Davis et al. that runs in linear time for (non-extended) regexes, we study efficient backtracking matching for regexes with two common extensions, namely look-around and atomic grouping. We present linear-time backtracking matching algorithms for these extended regexes. Their efficiency relies on memoization, much like the one by Davis et al.; we also strive for smaller memoization tables by carefully trimming their range. Our experiments -- we used some real-world regexes with the aforementioned extensions -- confirm the performance advantage of our algorithms.