Better algorithms for matching patterns with repeated parts in text
Improved Regular Expression Matching with Simple Backreferences
Data Structures and Algorithms
Summary
Regular expressions with backreferences let you match parts of text that repeat exactly, like finding a word and then that same word again. Matching these patterns is generally hard and slow, but the authors focus on a simpler case with one repeated part. They improve previous methods to make the matching faster and use less memory. Their approach also extends to slightly more complex patterns, making it easier to handle some real-world text searches efficiently.
What this means in practice
- •For software developers: Improve text processing tasks in programming tools that use repeated pattern matching, providing faster and more memory-efficient matching of single-group backreferences.
- •For database engineers: Enhance query engines that support advanced text search with repeated pattern constraints, optimizing performance for one group repeated multiple times.
Authors
Philip Bille, Inge Li Gørtz, Rikke Schjeldrup Jessen
Abstract
A regular expression with backreferences (rewb) specifies a set of strings formed by characters combined with concatenation, union, star operators, and backreferences. A backreference consists of a capturing group $(\cdot)_i$ and a reference $\backslash i$. The substring matched by the reference must match the substring matched by the corresponding capturing group. Given a rewb $R$ and a string $Q$, the rewb matching problem is to decide whether $Q$ is one of the strings specified by $R$. In full generality, rewb matching is NP-complete, but efficient solutions exist for various subclasses. In the paper, we focus on rewb containing a single capturing group and $k$ references. For this class, Uezato~[CPM 2026] gave an $O((k n^2 m^2)$ time and $O(n^2m^2)$ space algorithm, where $m$ is the length of the regular expression $R$ and $n$ is the length of the string $Q$. For the special case of $k=1$, Nogami and Terauchi~[MFCS 2025] gave an $O(n^2m^2)$ time and $O(n+ m^2)$ space algorithm. On the other hand, Nogami, Nakamura, and Terauchi~[arXiv 2026] gave a conditional lower bound, showing that we cannot solve the problem in $O(n^{2-ε} \mathrm{poly}(m))$ for any $ε> 0$ assuming the orthogonal vector hypothesis. Our main result is a new algorithm that runs in $O(n^2m)$ time and uses $O(nm)$ space. This improves the above results (by a factor of $km$ and $m$, respectively) and the former's space bound (by a factor of $nm$). We also show how to extend our algorithm to handle a slightly more general class of ordered and single-nested rewbs.