Linear Time Subsequence and Supersequence Regex Matching

Abstract

It is well-known that checking whether a given string $w$ matches a given regular expression $r$ can be done in quadratic time $O(|w|\cdot |r|)$ and that this cannot be improved to a truly subquadratic running time of $O((|w|\cdot |r|{)}^{1-\hat{I}\mu })$ assuming the strong exponential time hypothesis (SETH). We study the related problem that asks whether $w$ has a \emph{subsequence} that matches $r$, and we show that surprisingly this task admits an algorithm that runs in linear time, i.e., in $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 \emph{quantitative} problems of computing a longest subsequence or shortest supersequence of $w$ that matches $r$ can be solved with the same complexity as the classical longest common subsequence or shortest common supersequence problems, i.e., in $O(|w|\cdot |r|)$, and conditionally not in $O((|w|\cdot |r|{)}^{1-\hat{I}\mu })$. 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|\cdot |r|)$, but not in $O((|w|\cdot |r|{)}^{1-\hat{I}\mu })$ assuming SETH. We last study the complexity of the \emph{universal} problem that asks if \emph{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.

33 pages. Full version including all proofs