145 citations · 240 across the 14 of their papers we have counts for
7 papers · 1 filter
Space-Efficient Construction of Compressed Suffix Trees
Nicola Prezza, Giovanna Rosone
We show how to build several data structures of central importance to string processing, taking as input the Burrows-Wheeler transform (BWT) and using small extra working space. Le…
String Attractors and Combinatorics on Words
Sabrina Mantaci, Antonio Restivo, Giuseppe Romana +2
The notion of \emph{string attractor} has recently been introduced in [Prezza, 2017] and studied in [Kempa and Prezza, 2018] to provide a unifying framework for known dictionary-ba…
The Alternating BWT: an algorithmic perspective
Raffaele Giancarlo, Giovanni Manzini, Antonio Restivo +2
The Burrows-Wheeler Transform (BWT) is a word transformation introduced in 1994 for Data Compression. It has become a fundamental tool for designing self-indexing data structures,…
Combinatorial Algorithms for String Sanitization
Giulia Bernardini, Huiping Chen, Alessio Conte +6
String data are often disseminated to support applications such as location-based service provision or DNA sequence analysis. This dissemination, however, may expose sensitive patt…
Elastic-Degenerate String Matching via Fast Matrix Multiplication
Giulia Bernardini, Paweł Gawrychowski, Nadia Pisanti +2
An elastic-degenerate (ED) string is a sequence of sets of strings of total length , which was recently proposed to model a set of similar sequences. The ED string matching…
A New Class of Searchable and Provably Highly Compressible String Transformations
Raffaele Giancarlo, Giovanni Manzini, Giovanna Rosone +1
The Burrows-Wheeler Transform is a string transformation that plays a fundamental role for the design of self-indexing compressed data structures. Over the years, researchers have…