Regular Expression Matching with Ordered Linear Backreferences
Philip Bille, Inge Li Gørtz, Rikke Schjeldrup Jessen
原文摘要
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 one or more references $\backslash i$. The substring matched by the reference must match the same substring that was matched by the corresponding capturing group. We focus on a subclass, which we call ordered linear rewbs where the references and capturing groups occur only outside star and union operators. Furthermore, we require that all references to a capturing group occur before the next capturing group in the rewb. In full generality, rewb matching is NP-complete, but efficient solutions exist for various subclasses. For linear rewbs with one capturing group and $k$ references, 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 improved algorithm that runs in $O(n^2m+n^2k\log n)$ time and uses $O(nm)$ space, and handles the more general case of ordered linear rewbs with multiple capturing groups.
cs.DS