Showing cs.DSShow all
3 papers · 1 filter
cs.DS2026
Linear Time Subsequence and Supersequence Regex Matching
Antoine Amarilli, Bartlomiej Dudek, Florin Manea +2
It is well-known that checking whether a given string matches a given regular expression can be done in quadratic time and that this cannot be improved to…
cs.DS2024
Revisiting Weighted Information Extraction: A Simpler and Faster Algorithm for Ranked Enumeration
Pawel Gawrychowski, Florin Manea, Markus L. Schmid
Information extraction from textual data, where the query is represented by a finite transducer and the task is to enumerate all results without repetition, and its extension to th…
cs.DS2024
Subsequences With Generalised Gap Constraints: Upper and Lower Complexity Bounds
Florin Manea, Jonas Richardsen, Markus L. Schmid
For two strings u, v over some alphabet A, we investigate the problem of embedding u into w as a subsequence under the presence of generalised gap constraints. A generalised gap co…