29 citations · 45 across the 41 of their papers we have counts for
Showing 2020Show all
3 papers · 1 filter
cs.DS2020
Substring Complexity in Sublinear Space
Giulia Bernardini, Gabriele Fici, Paweł Gawrychowski +1
Shannon's entropy is a definitive lower bound for statistical compression. Unfortunately, no such clear measure exists for the compressibility of repetitive strings. Thus, ad hoc m…
cs.DS2020
String Sanitization Under Edit Distance: Improved and Generalized
Takuya Mieno, Solon P. Pissis, Leen Stougie +1
Let be a string of length over an alphabet , be a positive integer, and be a set of length- substrings of . The ETFS problem asks us to construct…
cs.DS2020
Pattern Masking for Dictionary Matching
Panagiotis Charalampopoulos, Huiping Chen, Peter Christen +4
In the Pattern Masking for Dictionary Matching (PMDM) problem, we are given a dictionary of strings, each of length , a query string of length , a…