Linear Time Subsequence and Supersequence Regex Matching

Antoine Amarilli, Bartłomiej Dudek, Florin Manea, Tina Ringleb, Markus L. Schmid · 2025

Read Linear Time Subsequence and Supersequence Regex Matching by Antoine Amarilli, Bartłomiej Dudek, Florin Manea, Tina Ringleb, Markus L. Schmid (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-16288.txt.

Introduction

Checking whether a text string fits a pattern is a basic task in computing, and the classic method takes time that grows with both lengths. Antoine Amarilli and co-authors study a looser version of the task in a 2025 paper. They ask whether some subsequence of the string, formed by deleting letters, fits the pattern.

Against expectations, this looser task can be solved in time that grows only in a straight line with the inputs. The same fast result holds when the goal flips to a supersequence, a longer string that contains the given one. The authors also solve the best-length versions of both tasks at the classic cost. Other ways of loosening the match, they show, stay as hard as the classic task.

Catalog record

CREATORAntoine Amarilli, Bartłomiej Dudek, Florin Manea, Tina Ringleb, Markus L. Schmid
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE131 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-16288

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Linear Time Subsequence and Supersequence Regex Matching Antoine Amarilli, Bartłomiej Dudek, Florin Manea, Tina Ringleb, Markus L. Schmid Abstract It is well-known that checking whether a given string w w matches a given regular expression r r can be done in quadratic time O ⁡ ( | w | ⋅ | r | ) O(|w|\cdot|r|) and that this cannot be improved to a truly subquadratic running time of O ⁡ ( ( | w | ⋅ | r | ) 1 − ϵ ) O((|w|\cdot|r|)^{1-\epsilon}) assuming the strong exponential time hypothesis (SETH). We study the related problem that asks whether w w has a subsequence that matches r r , and we show that surprisingly this task admits an algorithm that runs in linear time, i.e., in O ⁡ ( | w | + | r | ) O(|w|+|r|) . We further show that the same holds if we ask for a supersequence instead of a subsequence. Moreover, we show that the quantitative problems of computing a longest subsequence or shortest supersequence of w w that matches r r can be solved with the same complexity as the classical longest common subsequence or shortest common supersequence problems, i.e., in O ⁡ ( | w | ⋅ | r | ) O(|w|\cdot|r|) , and conditionally not in O ⁡ ( ( | w | ⋅ | r | ) 1 − ϵ ) O((|w|\cdot|r|)^{1-\epsilon}) . By contrast, if instead of subsequences or supersequences we consider other string relations like the infix, prefix, left-extension, or extension relations, then all the corresponding problems (both quantitative and non-quantitative) have the same complexity as classical regex matching, i.e., they can also be solved in O ⁡ ( | w | ⋅ | r | ) O(|w|\cdot|r|) , but not in O ⁡ ( ( | w | ⋅ | r | ) 1 − ϵ ) O((|w|\cdot|r|)^{1-\epsilon}) assuming SETH. We last study the complexity of the universal problem that asks if all subsequences (or supersequences, infixes, prefixes, left-extensions or extensions) of an input string satisfy a given regular expression. For these problems, we show polynomial upper bounds (along with matching conditional lower bounds) for the infix and prefix relations, but PSPACE-completeness for the extension, left-extension and supersequence relations, and coNP-completeness for the subsequence relation. 1 Introduction Regular expressions (also called regex) were first introduced by Kleene in 1956 [ 41 ] as a theoretical concept and quickly found their way into practice with the classical construction by Thompson [ 64 ] . Nowadays, they are a standard tool for text processing and data retrieval tasks, and they constitute computational primitives in virtually all modern programming languages (see the standard textbook [ 28 ] ). The most important problem about regular expressions is their matching problem , i.e., checking whether a given regular expression r matches a given string w . One of the two main algorithmic approaches to this problem is still Thompson’s original construction: transform r into a nondeterministic finite automaton with \varepsilon -transitions (or \varepsilon NFA) A in linear time, and then simulate A on w in time O(|w|\cdot|A|) . (The other approach is to transform r into a deterministic finite automaton or DFA, whose size is generally exponential in r .) In addition to their well-known applications as text analysis tools, regular expressions are also used in many different areas and are at the core of several data management principles: graph databases [ 8 ] , information extraction [ 24 ] , complex event processing [ 35 ] , network monitoring [ 48 ] , financial fraud detection [ 63 ] , infrastructure security [ 45 ] , etc. The problem of regular expression matching (and the strongly related problem of NFA acceptance) is also one of the base problems investigated in fine-grained complexity [ 11 , 14 , 15 ] . A classical result in this area is that the long-standing quadratic upper bound of O(|w|\cdot|r|) for matching is optimal in the sense that it cannot be improved to truly subquadratic complexity of O((|w|\cdot|r|)^{1-\epsilon}) unless the strong exponential time hypothesis (SETH) fails: see [ 11 ] . 1 1 1 Note that a running time O(m\cdot n) for input sizes m and n is also called rectangular in the literature to distinguish from a quadratic running time of the form O(n^{2}) . In this paper, we use nevertheless the term quadratic for running time O(m\cdot n) and subquadratic for running time O((m\cdot n)^{1-\epsilon}) . We contribute to the research on regex matching by exploring the following new angle. Instead of asking whether the whole input string w matches the regex r , we ask whether w has a subsequence that matches r ; or a supersequence that matches r ; or, more generally, whether r matches some string u with u\preceq w , where \preceq is a fixed string relation (and classical regex matching is then the case when \preceq is the equality relation). While technically any possible string relation \preceq instantiates a \preceq -version of the regex matching problem, we focus on relations that are relevant for string matching: the subsequence relation ( x_{1}x_{2}\ldots x_{n}\preceq_{\mathsf{sub}}w\Leftrightarrow w=w_{0}\,x_{1}\,w_{1}\,x_{2}\ldots x_{n}\,w_{n} ), supersequence relation ( u\preceq_{\mathsf{sup}}w\Leftrightarrow w\preceq_{\mathsf{sub}}u ), infix relation ( u\preceq_{\mathsf{in}}w\Leftrightarrow w=vuv^{\prime} ), prefix relation ( u\preceq_{\mathsf{pre}}w\Leftrightarrow w=uv ), left-extension relation ( u\preceq_{\mathsf{lext}}w\Leftrightarrow u=vw ), and extension relation ( u\preceq_{\mathsf{ext}}w\Leftrightarrow w\preceq_{\mathsf{in}}u ). 1.1 Our Results Our main focus is on the subsequence and supersequence relations, and our first contribution is to show that the complexity of regular expression matching can be substantially improved when performed with these relations. Namely, we show that given a regex r and string w , we can check in time O(|w|+|r|) whether some subsequence of w matches r , or whether some supersequence of w matches r . We believe that this tractability result is quite surprising, and it turns out to be in strong contrast to the same problem for other string relations (infix, prefix, left-extension and extension), or for regex matching in the usual sense. Indeed, in all these cases, we show that the complexity of O(|w|\cdot|r|) is optimal in the sense explained above (assuming SETH). Our linear time upper bound for subsequence and supersequence matching is achieved by transforming the regex r into an \varepsilon NFA A that accepts w if and only if w has a subsequence (or supersequence) that matches r , following a known construction in the context of so-called upward and downward closures [ 10 ] . We then exploit special properties of A that allow us to decide whether it accepts w in linear time. It is then not very difficult to improve the bound and make it linear in the input word: however, more effort is needed to also ensure that the complexity is linear in the regex (in particular in the setting where the input alphabet is not constant), and achieve the optimal complexity of O(|w|+|r|) . \preceq -matching min/max-variant universal-variant subsequence O(|w|+m) O(|w|m) coNP supersequence O(|w|+m) O(|w|m) PSPACE infix O(|w|m) O(|w|m) O(|w|^{2}m) prefix O(|w|m) O(|w|m) O(|w|m) extension O(|w|m) O(|w|m) PSPACE left-extension O(|w|m) O(|w|m) PSPACE Table 1: Upper bounds for the different problem variants. The problem \preceq -matching is to check whether there is a string u\preceq w

Read the complete text