Source-linked AI summary
Improved Regular Expression Matching with Simple Backreferences
Philip Bille, Inge Li Gørtz, Rikke Schjeldrup Jessen
TL;DR
Rewb matching asks whether an input string belongs to the language specified by a regular expression with backreferences, a problem that is NP-complete in full generality. The paper develops an interval-tree-based algorithm for one capturing group and multiple references, achieving improved bounds and extending them to ordered, single-nested rewbs.
Problem
Rewb matching is NP-complete in full generality, motivating efficient algorithms for the subclass with one capturing group and one or more references.
Method
The algorithm combines suffix-tree enumeration of candidate capturing-group substrings with interval-tree propagation of feasible match endpoints through Thompson automata.
Results
O(n^2m) time and O(nm) space solve matching for one capturing group and k references, improving prior time and space bounds.
Takeaways & Limitations
The same O(n^2m)-time and O(nm)-space bounds extend to ordered, single-nested rewbs.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper studies matching for rewbs with one capturing group and multiple references, introducing an algorithm with improved time and space bounds and an extension to ordered, single-nested rewbs.
- Rewb matching is used in text processing applications including intrusion detection, graph-database querying, software testing, symbolic execution, and string-constraint solving.
- O(n^2m) time and O(nm) space solve matching for a rewb with one capturing group and k references.
- The new bound improves prior results by factors of km in time and nm in space, and improves the k=1 time bound by factor m.
- The extension covers ordered, single-nested rewbs while retaining O(n^2m) time and O(nm) space.
- The algorithm combines suffix-tree enumeration of capturing-group substrings with an interval tree that propagates feasible match endpoints.
2 Preliminaries
The preliminaries define strings, finite automata, Thompson NFAs, and suffix trees as the structures used to represent expressions and process input substrings.
- Strings are sequences of characters whose substrings are contiguous character concatenations, with an empty substring denoted ε.
- A finite automaton is an edge-labeled directed graph with designated start and accepting states, and it accepts when a matching path connects them.
- State-set transitions test acceptance by iteratively updating reachable states for each input character, including epsilon transitions.
- A Thompson NFA accepts exactly the language of a regular expression, has at most 2m states and 4m transitions, and can be constructed in O(m) time.
- Regular-expression matching using Thompson NFAs takes O(nm) time and O(m) space under the state-set transition algorithm.
- A suffix tree is the compacted trie of all suffixes of Q, with leaves represented by their starting indices and nodes representing path-label strings.
3 Interval Trees
The interval tree organizes dyadic substrings of the input and stores automaton state sets that support efficient matching across arbitrary endpoints. It can be constructed in O(n^2m) time and O(nm) space.
- 3 Interval Trees: An interval tree is a complete binary tree whose nodes represent dyadic intervals of the input string.Leaves represent length-1 intervals, while a node at height k represents an interval of length 2^k.
- 3 Interval Trees: Each node stores its interval boundaries, midpoint, and bit-vector state sets for substrings extending toward the midpoint from either side.The left and right match-state sets record Thompson-automaton states reachable from the start or able to reach an accepting state.
- 3 Interval Trees: The interval tree is computed in O(n^2m) time and stored in O(nm) space.The time follows from computing match sets from every input index, while the space bound sums bit-vector storage across tree levels.
- 3 Interval Trees: The tree computes all left and right match sets by propagating state transitions through the Thompson automaton and its reverse.For each input index, the construction records state sets at relevant ancestor midpoints and computes the reverse-direction sets symmetrically.
4 Regular Expressions with a Single Reference
The single-reference matcher enumerates candidate substrings with a suffix tree and tests surrounding matches through interval-tree state sets. Its analysis yields O(n^2m) time and O(nm) space.
- 4.1 Interval Tree Traversal: For each candidate q, prefix and suffix match indices identify boundaries matching e0 concatenated with q and q concatenated with e2.These indices are partitioned into left and right halves for interval-tree traversal.
- 4.1 Interval Tree Traversal: The traversal unions state sets from feasible left and right boundaries and accepts when their intersection is nonempty.A nonempty intersection provides a path through the automaton for e1 between the two q occurrences.
- 4.2 Algorithm: Preprocessing builds Thompson NFAs, the interval tree, the suffix tree, and prefix and suffix boundary sets before candidate processing.The prefix and suffix sets are computed from automata for e0 and e2, while the interval tree is built for e1.
- 4.2 Algorithm: The algorithm enumerates substrings q matching e with a suffix tree, records their occurrences, and processes each candidate by traversing the interval tree for e1.Suffix-tree traversal uses Thompson-NFA state sets to identify matching substrings and construct occurrence lists.
- 4.3 Analysis: O(n^2m) time and O(nm) space solve matching for a single capturing group and single reference.The algorithm processes matching substrings and its analysis establishes these overall bounds.
5 Regular Expressions with Multiple References
The algorithm handles a single capturing group with multiple references by chaining interval-tree traversals, propagating feasible prefix positions between references. It runs in O(n^2m) time and O(nm) space.
- O(n^2m) time and O(nm) space are maintained for patterns with one capturing group and multiple references.
- For each matching substring q, sequential traversals of interval trees propagate feasible prefix matches across the k references.Each traversal uses outputs from the preceding tree as its next prefix-match indices.
- At each tree node, the algorithm partitions prefix positions and q occurrences, unions reachable left states, and intersects them with right states.A nonempty intersection adds the resulting endpoint to nextprefixmatchq,h.
- After processing q, its final propagated positions enter endpoints; matching succeeds when an endpoint is followed by a suffix match.The correctness argument establishes that endpoints contains exactly the prefixes matching the repeated-reference portion.
- Suffix-tree enumeration supplies every distinct substring q matching the capturing-group expression together with all its occurrences.Prefix and suffix sets are computed separately for the surrounding regular expressions before interval-tree processing.
- The analysis bounds interval-tree traversal across all matching substrings by O(n^2m), while endpoint generation contributes only O(n^2).
6 Ordered and Single-Nested Regular Expressions
The paper extends the algorithm to ordered, single-nested rewbs by processing their component subexpressions sequentially. The extension preserves O(n^2m) time and O(nm) space.
- O(n^2m) time and O(nm) space solve matching for ordered, single-nested regular expressions.The class consists of sequential subexpressions, each containing one capturing group and its ordered references.
- Each subexpression is processed by finding matching captured substrings and traversing its corresponding interval trees.The resulting endpoint indices become prefix-match indices for the next subexpression.
- The algorithm initializes each traversal from prefixset, the preceding component’s endpoints, or the preceding interval tree’s propagated matches, depending on the case.
- For component Eℓ, endpointsℓ records exactly the positions where the prefix matches E0 through Eℓ.Lemma 9 establishes this invariant inductively from endpointsℓ−1.
- After the final component, matching succeeds when an endpoint is followed by a suffix match for the trailing expression.
- The runtime sums interval-tree construction and traversal, automaton processing, and substring enumeration across all nested components.The corresponding space bound stores the interval trees and automata within O(nm).