Efficient Matching of Some Fundamental
Regular Expressions with Backreferences

A regular expression is a convenient way to specify a language (i.e., a set of strings) using concatenation ($\cdot$), disjunction ($\mid$) and iteration ($\ast$). The regular expression matching problem (also known as regular expression membership testing) asks whether a given string belongs to the language of a given regular expression. This problem is of practical importance due to its widespread use in real-world applications, particularly in format validation and pattern searching. In 1968, Thompson presented a solution to this problem that runs in $O(nm)$ time where $n$ denotes the length of the input string and $m$ the length of the input regular expression [46]. We refer to his method, which constructs a nondeterministic finite automaton (NFA) and simulates it, as NFA simulation.

The matching problem of real-world regular expressions becomes increasingly complex due to its practical extensions such as lookarounds and backreferences. Unfortunately, reducing the matching of real-world regular expressions to that of pure ones is either inefficient or impossible. In fact, although adding positive lookaheads (a type of lookaround) does not increase the expressive power of regular expressions [31, 7], the corresponding NFAs can inevitably become enormous [30]. Worse still, adding backreferences makes regular expressions strictly more expressive, meaning that an equivalent NFA may not even exist.¹¹1The rewb ${({(a|b)}^{\ast })}_1\backslash 1$ specifies $\{ww\mid w\in {\{a,b\}}^{\ast }\}$, which is non-context-free (and therefore non-regular).

Nevertheless, most modern programming languages, such as Java, Python, JavaScript and more, support lookarounds and backreferences in their standard libraries for string processing. The most widely used implementation for the real-world regular expression matching is backtracking [44], an algorithm that is easy to implement and extend. On the other hand, the backtracking implementation suffers from a major drawback in that it takes exponential time in the worst case with respect to the input string length. This exponential-time behavior poses the risk of ReDoS (regular expression denial of service), a type of DoS attack that exploits heavy regular expression matching to cause service downtime, making it a critical security issue (refer to Davis et al. [14] for details on its history and case studies). In response, RE2, a regular expression engine developed by Google, has deferred supporting lookarounds and backreferences, thereby ensuring $O(nm)$ time complexity using NFA simulation.²²2The development team declares, “Safety is RE2’s raison d’être.” [47]

Regarding lookarounds, several recent papers have proposed groundbreaking $O(nm)$-time solutions to the matching problem of regular expressions with lookarounds [29, 21, 5], yet regarding backreferences, the outlook is bleak. The matching problem of regular expressions with backreferences (rewbs for short) is well known for its theoretical difficulties. Aho showed that the rewb matching problem is NP-complete [2]. Moreover, rewbs can be considered a generalization of Angluin’s pattern languages (also known as patterns with variables) [3]; even when restricted to this, its matching problem is NP-complete with respect to the lengths of both a given string and a given pattern [3, 16, 40], and its NP-hardness [18] as well as W[1]-hardness [19] are known for certain fixed parameter settings. The best-known matching algorithm for rewbs with at most $k$ capturing groups runs in $O(n^{2k+2}m)$ time [41, 42] (With a slight modification, the time complexity can be reduced in $O(n^{2k+1}m)$ time; see Section 4).

Therefore, the existence of an efficient worst-case time complexity algorithm that works for any rewb seems unlikely, necessitating researchers to explore efficient algorithms that work for some subset of rewbs [39, 42, 20]. Nevertheless, all existing solutions either have high worst-case time complexity or impose non-trivial constraints on the input rewbs, and finding a good balance between efficiency and generality remains an open issue.

To bridge this gap, we present an efficient matching algorithm for rewbs of the form $e_0{(e)}_1{e}_1\backslash 1e_2$, where $e_0,e,e_1,e_2$ are pure regular expressions, which are fundamental and frequently encountered in practical applications. While the best-known algorithm for these rewbs is the one stated above and it takes $O(n^{4}m)$ (or $O(n^{3}m)$) time because $k=1$ for these rewbs, our algorithm runs in $O(n^2{m}^2)$ time, improving the best-known time complexity for these rewbs with respect to the input string length $n$ from cubic to quadratic. The key appeal of this improvement lies in the replacement of the input string length $n$ with the expression length $m$. Because $n$ is typically much larger than $m$, this improvement is considerable.

These rewbs are of both practical and theoretical interest. From a practical perspective, these rewbs account for a large proportion of the actual usage of backreferences. In fact, we have confirmed that, among the dataset collected in a large-scale empirical study conducted by Davis et al. [14], which consists of real-world regular expressions used in npm and PyPI projects, approximately 57% (1,659/2,909) of the non-pure rewbs³³3Non-pure rewbs are rewbs that use backreferences. Note that rewbs, in general, also include ones that do not use backreferences (i.e., pure regular expressions). are of this form [34].

Additionally, the matching problem of rewbs of this form is a natural generalization of a well-studied foundational problem, making it theoretically interesting. A square (also known as tandem repeat) is a string $\alpha \alpha$ formed by juxtaposing the same string $\alpha$. The problem of deciding whether a given string contains a square is of interest in stringology, and has been well studied [28, 12]. The rewb matching considered in this paper can be viewed as a generalization of the problem by regular expressions.⁴⁴4The problem is an instance of our rewb matching problem where $e_0,e,e_2={\mathrm{\Sigma }}^{\ast }$ and $e_1=\epsilon$.

We now provide an overview of our new algorithm. A novel aspect of the algorithm is that, unlike previous algorithms for rewb matching or square finding, it combines ideas from both stringology and automata theory. Our algorithm utilizes the suffix array of the input string to efficiently enumerate candidates for backreferenced substrings (i.e., the contents of $\backslash 1$). Once a candidate $\alpha$ is fixed, the matches whose backreferenced substring is $\alpha$ can be examined in $O(nm)$ time in almost the same way as NFA simulation. Because the number of candidate substrings is $\mathrm{\Theta }(n^2)$, this gives an $O(n^{3}m)$-time algorithm (see Remark 11 for details). Next, we improve this baseline algorithm by extending the NFA simulation to simultaneously examine all matches whose backreferenced substrings are either a right-maximal repeat or its extendable prefixes, instead of examining each candidate individually. Because the new NFA simulation requires $O(m^2)$ time at each step and the number of right-maximal repeats is at most $n-1$, our algorithm runs in $O(n^2{m}^2)$ time.

A key challenge is how to do all the examinations within time linear in $n$ for each fixed right-maximal repeat $\alpha$. To address this, we incorporate two techniques from automata theory, injection and summarization. Each of these techniques is fairly standard on its own (see Section 4 for their applications in prior work), but the idea of combining them is, to our knowledge, novel. Additionally, we leverage a subtle property of $\alpha$-extendable prefixes to do the examinations correctly within time linear in $n$ even when occurrences of $\alpha$ may overlap (see Section 3.2).

The rest of the paper is organized as follows. Section 2 defines the key concepts in this paper, namely NFA simulation and right-maximal repeats. Section 3 presents our algorithm, which is the main contribution of this paper. Section 4 discusses related work and Section 5 presents the conclusion and future work. Omitted proofs are available in the full version [36].

Let $\mathrm{\Sigma }$ be a set called an alphabet, whose elements are called characters. A string $w$ is a finite sequence $a_1\mathrm{\cdots }{a}_n$ of characters $a_1,\mathrm{\dots },a_n$, and we write $|w|$ for the number $n$ of characters in the sequence. The empty string is written as $\epsilon$. For integers $i,j\ge 0$, we write $[i,j]$ for the set of integers between $i$ and $j$. For $i,j\in [1,n]$, we write $w[i..j]$ for the substring $a_i\mathrm{\cdots }{a}_j$. In particular, (1) $w[i]:=w[i..i]=a_i$ is called the character at position $i$, (2) $w[..i]:=w[1..i]$ is called the prefix up to position $i$ and (3) $w[i..]:=w[i..n]$ is called the suffix from position $i$. We regard $w[i+1..i]$ as $\epsilon$. A regular expression $e$ and its language denoted by $L(e)$ are defined in the standard way.

First, we define the matching problem for rewbs of the form mentioned earlier.

A regular expression $e$ matches a string $w$ if $w\in L(e)$. The matching problem for regular expressions is defined to be the problem of deciding whether a given regular expression matches a given string, and similarly for rewbs (of the form considered in this paper).

Next, we review a classical solution of the regular expression matching.

The transitive closure of a transition relation $\delta$ with the second argument fixed at $\epsilon$ is called $\epsilon$-closure operator and written as ${\mathrm{cl}}_{\epsilon }$. Further, we lift ${\mathrm{cl}}_{\epsilon }:Q\to 𝒫(Q)$ to $𝒫(Q)\to 𝒫(Q)$ by taking unions, i.e., ${\mathrm{cl}}_{\epsilon }(S):={\bigcup }_{q\in S}{\mathrm{cl}}_{\epsilon }(q)$. For a state $q$ and a character $a$, we define $\mathrm{\Delta }(q,a)$ as ${\mathrm{cl}}_{\epsilon }(\delta (q,a))$, which informally consists of states reachable by repeating $\epsilon$-moves from states that are reachable from $q$ by $a$. As before, we extend $\mathrm{\Delta }$ by setting $\mathrm{\Delta }(S,a):={\bigcup }_{q\in S}\mathrm{\Delta }(q,a)$. Also, for a string $w$, we define $\mathrm{\Delta }(S,w)$ as $\mathrm{\Delta }(S,\epsilon ):=S$ and $\mathrm{\Delta }(S,wa):=\mathrm{\Delta }(\mathrm{\Delta }(S,w),a)$. Thus, the language $L(N)$ of an NFA $N$ is the set of strings $w$ such that $\mathrm{\Delta }({\mathrm{cl}}_{\epsilon }(q_0),w)\cap F\ne \mathrm{\varnothing }$.

The NFA simulation of $N$ on a string $w$ of length $n$ is the following procedure for calculating $\mathrm{\Delta }({\mathrm{cl}}_{\epsilon }(q_0),w)$ [46]. First, $S^{(0)}:={\mathrm{cl}}_{\epsilon }(q_0)$ is calculated, and then $S^{(i)}:=\mathrm{\Delta }(S^{(i-1)},w[i])$, called the simulation set at position $i$, is sequentially computed from $S^{(i-1)}$ for each $i\in [1,n]$. We have $w\in L(N)\iff S^{(n)}\cap F\ne \mathrm{\varnothing }$.

This gives a solution to the regular expression matching in $O(nm)$ time and $O(m)$ space where $n$ is the length of the input string $w$ and $m$ that of the input regular expression $e$. First, convert $e$ to an equivalent NFA $N_e$ whose number of states and transitions are both $O(m)$ using the standard construction, then run the NFA simulation of $N_e$ on $w$. Finally, check whether the last simulation set $S^{(n)}$ contains any accept state of $N_e$. Each step of the NFA simulation can be done in $O(m)$ time using breadth-first search. Also, the procedure can be implemented in $O(m)$ space by reusing the same memory for each $S^{(i)}$.

Next, we review right-maximal repeats and extendable prefixes. Let $w$ be a string. A nonempty string $\alpha$ occurs at position $i$ in $w$ if $w[i..i+|\alpha |-1]=\alpha$. Two distinct occurrences of $\alpha$ at positions overlap if . A repeat of $w$ is a nonempty string that occurs in $w$ more than once. A repeat $\alpha$ is called right-maximal if $\alpha$ occurs at two distinct positions $i,j$ such that the right-adjacent characters are different (i.e., $w[i+|\alpha |]\ne w[j+|\alpha |]$). In the special case when $\alpha$ occurs at the right end of $w$, we consider it to have a right-adjacent character distinct from all other characters when defining right-maximality. For example, the right-maximal repeats of mississimiss are i, iss, issi, miss, s, si, ss and ssi (miss, iss, ss are due to the special treatment).⁵⁵5This shows that, contrary to what the word suggests, a right-maximal repeat may contain another right-maximal repeat. In fact, the repeat iss and its proper substrings i, s and ss are all right-maximal. In general, the number of repeats of a string of length $n$ is $\mathrm{\Theta }(n^2)$, while that of right-maximal repeats is at most $n-1$ [23].

For any non-right-maximal repeat $\alpha$, all the right-adjacent positions of the occurrences of $\alpha$ have the same character. By repeatedly extending $\alpha$ with this, we will obtain the right-maximal repeat, denoted by $\overrightarrow{\alpha }$. This notation $\overrightarrow{\alpha }$ follows that of [25, 45, 33]. We define $\overrightarrow{\alpha }:=\alpha$ for a right-maximal repeat $\alpha$. A prefix $\beta$ of $\alpha$ such that $\overrightarrow{\beta }=\alpha$ is called $\alpha$-extendable prefix of $\alpha$. Note that $\alpha$ itself is $\alpha$-extendable. Two distinct occurrences of an $\alpha$-extendable prefix $\beta$ are $\alpha$-separable in $w$ if the two $\alpha$’s extended from the $\beta$’s have no overlap.

Finally, we mention the enumeration subroutine used in our algorithm. Abouelhoda et al. presented an $O(n)$-time enumeration algorithm for right-maximal repeats [1]. By slightly modifying this, we obtain an $O(n^2)$-time algorithm EnumRM that enumerates each right-maximal repeat $\alpha$ with the sorted array ${\mathrm{𝖨𝖽𝗑}}_{\alpha }$ of all starting positions of the occurrences of $\alpha$ (see the full version [36] for details). We call ${\mathrm{𝖨𝖽𝗑}}_{\alpha }$ the occurrence array of $\alpha$ in $w$.

In this section, we show an efficient matching algorithm for rewbs of the form $e_0{(e)}_1{e}_1\backslash 1e_2$, which is the main contribution of this paper.

Let $r$ be a rewb $e_0{(e)}_1{e}_1\backslash 1e_2$ and $w$ be a string. The overview of our matching algorithm for $r$ and $w$ is as follows. We assume without loss of generality that $e$ does not match $\epsilon$ because we can check if $e$ matches $\epsilon$ and $e_0{e}_1{e}_2$ matches $w$ in $O(nm)$ time by ordinary NFA simulation. We show an $O(n(m_e+m_{e_1}^2))$-time and $O(n+m_e+m_{e_1}^2)$-space subprocedure $\text{Match}(\alpha ,{\mathrm{𝖨𝖽𝗑}}_{\alpha })$ ($\text{Match}(\alpha )$ for short) that takes a right-maximal repeat $\alpha$ and its occurrence array ${\mathrm{𝖨𝖽𝗑}}_{\alpha }$, and simultaneously examines all matches whose backreferenced substrings (i.e., the contents of $\backslash 1$) are $\alpha$-extendable prefixes of $\alpha$. Before defining Match, we state the property that characterizes its correctness:

Given this, the overall matching algorithm Main is constructed as follows. It first constructs an NFA $N_{e_1}$ equivalent to the middle subexpression $e_1$ and two Boolean arrays $\mathrm{𝖯𝗋𝖾}$ and $\mathrm{𝖲𝗎𝖿}$, which are necessary for Match. A Boolean array $\mathrm{𝖯𝗋𝖾}$ (resp. $\mathrm{𝖲𝗎𝖿}$) is the array which stores whether each prefix (resp. suffix) of $w$ is matched by $e_0$ (resp. $e_2$). More precisely, $\mathrm{𝖯𝗋𝖾}$ and $\mathrm{𝖲𝗎𝖿}$ are the arrays such that $\mathrm{𝖯𝗋𝖾}[i]=\mathrm{𝐭𝐫𝐮𝐞}\iff w[..i]\in L(e_0)$ for $i\in [0,n]$ and $\mathrm{𝖲𝗎𝖿}[j]=\mathrm{𝐭𝐫𝐮𝐞}\iff w[j..]\in L(e_2)$ for $j\in [1,n+1]$. Note that we can construct these arrays in $O(n(m_{e_0}+m_{e_2}))$ time and $O(n+\max \{m_{e_0},m_{e_2}\})$ space as mentioned in Remark 4. Then, it runs the $O(n^2)$-time and $O(n)$-space enumeration algorithm EnumRM from the final paragraph of the previous section. Each time EnumRM outputs $\alpha$ and ${\mathrm{𝖨𝖽𝗑}}_{\alpha }$, Match is executed with these as input and using $N_{e_1}$, $\mathrm{𝖯𝗋𝖾}$ and $\mathrm{𝖲𝗎𝖿}$. Main returns $\mathrm{𝐭𝐫𝐮𝐞}$ if $\text{Match}(\alpha )$ returns $\mathrm{𝐭𝐫𝐮𝐞}$ for some $\alpha$; otherwise, it returns $\mathrm{𝐟𝐚𝐥𝐬𝐞}$.

We first mention efficient solutions of the pure regular expression matching problem. The improvement of the $O(nm)$-time solution using NFA simulation was raised as an unsolved problem by Galil [22], but in 1992, Myers successfully resolved it in a positive manner [32]. Since then, further improvements have been made by researchers, including Bille [8, 9, 11]. On the other hand, Backurs and Indyk have shown that under the assumption of the strong exponential time hypothesis, no solution exists within $O({(nm)}^{1-ϵ})$ time for any $ϵ>0$ [4]. Recently, Bille and Gørtz have shown the complexity with respect to a new parameter, the total size of the simulation sets in an NFA simulation ${\sum }_{i=0}^n|S^{(i)}|$, in addition to $n$ and $m$ [10].

We next discuss prior work on the matching problem of rewbs. The problem can be solved by simulating memory automata (MFA), which are a model proposed by Schmid [41] with the same expressive power as rewbs. An MFA has additional space called memory to keep track of matched substrings. A configuration of an MFA $M$ with $k$ memories is a tuple $(q,u,(x_1,s_1),\mathrm{\dots },(x_k,s_k))$ where $q$ is a current state, $u$ is the remaining input string and $(x_j,s_j)$ ($j\in [1,k]$) is the pair of the content substring $x_j$ and the state $s_j$ of memory $j$. Therefore, the number of configurations of $M$ equivalent to a given rewb on a given string is $O(n^{2k+1}m)$. Because each step of an MFA simulation may involve $O(n)$ character comparisons, this gives a solution to the rewb matching problem that runs in $O(n^{2k+2}m)$ time. Davis et al. gave an algorithm with the same time complexity as this [15]. Furthermore, by precomputing some string indices as in this paper, a substring comparison can be done in constant time, making it possible to run in $O(n^{2k+1}m)$ time. Therefore, for the rewbs considered in this paper, these algorithms take time cubic in $n$ because $k=1$ for these rewbs, and our new algorithm substantially improves the complexity, namely, to quadratic in $n$.

Regarding research on efficient matching of rewbs, Schmid proposed the active variable degree (avd) of MFA and discussed the complexity with respect to avd [42]. Roughly, avd is the minimum number of substrings that needs to be remembered at least once per step in an MFA simulation. For example, in a simulation of an MFA equivalent to the rewb ${(a^{\ast })}_1\backslash 1{(b^{\ast })}_2\backslash 2$, after consuming the substring captured by ${(a^{\ast })}_1$ in the transition which corresponds to $\backslash 1$, configurations no longer need to keep the substring. In other words, it only needs to remember only one substring at each step of the simulation, and hence its avd is $1$. On the other hand, $\mathrm{avd}({(a^{\ast })}_1{(b^{\ast })}_2\backslash 1\backslash 2)$ is $2$. The avd of the rewbs considered in this paper is always $1$, but their method takes quartic (or cubic with the simple modification on MFA simulation outlined above) time for them. Freydenberger and Schmid proposed deterministic regular expression with backreferences and showed that the matching problem of deterministic rewbs can be solved in linear time [20]. The rewbs considered in this paper are not deterministic in general (for example, ${(a^{\ast })}_1\backslash 1$ is not).

Next, we mention research on efficient matching of pattern languages with bounded number of repeated variables. A pattern with variables is a string over constant symbols and variables. The matching problem for patterns is the problem of deciding whether a given string $w$ can be obtained from a given pattern $p$ by uniformly substituting nonempty strings of constant symbols for the variables of $p$. Note that, as remarked in the introduction, rewbs can be viewed as a generalization of patterns by regular expressions.

Fernau et al. discussed the matching problem for patterns with at most $k$ repeated variables [17]. A repeated variable of a pattern is a variable that occurs in the pattern more than once. In particular, for the case $k=1$, they showed the problem can be solved in quadratic time with respect to the input string length $n$. The patterns with one repeated variable and the rewbs considered in this paper are independent. While these patterns can use the variable more than twice, these rewbs can use regular expressions. Therefore, our contribution has expanded the variety of languages that can be expressed within the same time complexity with respect to $n$.

The algorithm by Fernau et al. [17] leverages clusters defined over the suffix array of an input string, which are related to right-maximal repeats. Moreover, it is similar to our approach in that it does the examination while enumerating candidate assignments to the repeated variable. The key technical difference is that, as demonstrated in their work, matching these patterns can be reduced to finding a canonical match by dividing the pattern based on wildcard variables. In contrast, matching the rewbs considered in this paper requires handling the general regular expression matching, particularly the substring matching of the middle expression $e_1$, which makes such a reduction not applicable even when the number of variable occurrences is restricted to $2$.

Regarding the squareness checking problem mentioned in the introduction, Main and Lorentz [28] and Crochemore [12] showed a linear-time solution on a given alphabet. However, both solutions rely on properties specific to square-free strings, and extending them to the matching problem considered in this paper seems difficult.

Finally, we mention related work on the techniques and concepts from automata theory and stringology used in this paper. A similar approach to using oracles such as $\mathrm{𝖯𝗋𝖾}$ and $\mathrm{𝖲𝗎𝖿}$ in NFA simulation is used in research on efficient matching of regular expressions with lookarounds [29, 5]. Summarization has been applied to parallel computing for pure regular expression matching [27, 24, 43]. Regarding injection, NFA simulation itself uses injection internally to handle concatenation of regular expressions. That is, an NFA simulation of $e_1{e}_2$ can be seen as that of $e_2$ that injects the $\epsilon$-closure of the initial state of the NFA $N_{e_2}$ whenever $e_1$ matches the input string read so far. Nonetheless, our use of these automata-theoretic techniques for efficient matching of rewbs is novel. In fact, to our knowledge, this paper is the first to propose an algorithm that combines these techniques.

The right-maximal repeats of a string are known to correspond to the internal nodes of the suffix tree of the string [23]. Kasai et al. first introduced a linear-time algorithm for traversing the internal nodes of a suffix tree using a suffix array [26]. Subsequently, Abouelhoda et al. introduced the concept of the LCP-interval tree to make their traversal more complete [1]. As stated in Section 2, our EnumRM that enumerates the right-maximal repeats with the sorted starting positions of their occurrences is based on their algorithm. To our knowledge, our work is the first to apply these stringology concepts and techniques to efficient matching of rewbs.

In this paper, we proposed an efficient matching algorithm for rewbs of the form $e_0{(e)}_1{e}_1\backslash 1e_2$ where $e_0,e,e_1,e_2$ are pure regular expressions, which are fundamental and frequently used in practical applications. As stated in the introduction and Section 4, it runs in $O(n^2{m}^2)$ time, improving the best-known time complexity for these rewbs when $n>m$. Because $n$ is typically much larger than $m$, this is a substantial improvement.

Our algorithm combines ideas from both stringology and automata theory in a novel way. The core of our algorithm consists of two techniques from automata theory, injection and summarization. Together, they enable the algorithm to do all the examination for a fixed right-maximal repeat and its extendable prefixes, which are concepts from stringology, instead of examining each individually. By further leveraging a subtle property of extendable prefixes, our algorithm correctly solves the matching problem in time quadratic in $n$.

A possible direction for future work is to further reduce the time complexity of the algorithm. A natural next step would be to use maximal repeats instead of right-maximal repeats. While this would not change the worst-case complexity with respect to $n$ [13, 38], it could lead to faster performance for many input strings. Another possible direction is to extend the algorithm to support more general rewbs as mentioned in Remark 2. The extension of our algorithm with support for other practical extensions such as lookarounds is also challenging.