7 citations · 10 across the 2 of their papers we have counts for
5 papers
Lower Bounds for the Number of Repetitions in 2D Strings
Paweł Gawrychowski, Samah Ghazawi, Gad M. Landau
A two-dimensional string is simply a two-dimensional array. We continue the study of the combinatorial properties of repetitions in such strings over the binary alphabet, namely th…
Cartesian Tree Matching and Indexing
Sung Gwan Park, Amihood Amir, Gad M. Landau +1
We introduce a new metric of match, called Cartesian tree matching, which means that two strings match if they have the same Cartesian trees. Based on Cartesian tree matching, we d…
Top Tree Compression of Tries
Philip Bille, Inge Li Gørtz, Paweł Gawrychowski +2
We present a compressed representation of tries based on top tree compression [ICALP 2013] that works on a standard, comparison-based, pointer machine model of computation and supp…
Fast entropy-bounded string dictionary look-up with mismatches
Paweł Gawrychowski, Gad M. Landau, Tatiana Starikovskaya
We revisit the fundamental problem of dictionary look-up with mismatches. Given a set (dictionary) of strings of length and an integer , we must preprocess it into a dat…
A Unified Algorithm for Accelerating Edit-Distance Computation via Text-Compression
Danny Hermelin, Gad M. Landau, Shir Landau +1
We present a unified framework for accelerating edit-distance computation between two compressible strings using straight-line programs. For two strings of total length having…