Linear Time Subsequence and Supersequence Regex Matching

Antoine Amarilli, Bartlomiej Dudek, Florin Manea +2

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…