Improved Regular Expression Matching with Simple Backreferences

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^2{m}^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^2{m}^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-\epsilon }\mathrm{poly}(m))$ for any $\epsilon >0$ assuming the orthogonal vector hypothesis. Our main result is a new algorithm that runs in $O(n^{2}m)$ 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.