13 citations · 30 across the 11 of their papers we have counts for
16 papers
Approximate Cartesian Tree Matching with One Difference
Bastien Auvray, Julien David, Samah Ghazawi +3
Cartesian tree pattern matching consists of finding all the factors of a text that have the same Cartesian tree than a given pattern. There already exist theoretical and practical…
Order-Preserving Squares in Strings
Paweł Gawrychowski, Samah Ghazawi, Gad M. Landau
An order-preserving square in a string is a fragment of the form where and is order-isomorphic to . We show that a string of length over an alphabet o…
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 Faster Construction of Greedy Consensus Trees
Paweł Gawrychowski, Gad M. Landau, Wing-Kin Sung +1
A consensus tree is a phylogenetic tree that captures the similarity between a set of conflicting phylogenetic trees. The problem of computing a consensus tree is a major step in p…
String Cadences
Amihood Amir, Alberto Apostolico, Travis Gagie +1
We say a string has a cadence if a certain character is repeated at regular intervals, possibly with intervening occurrences of that character. We call the cadence anchored if the…
Longest Common Extensions in Trees
Philip Bille, Pawel Gawrychowski, Inge Li Goertz +2
The longest common extension (LCE) of two indices in a string is the length of the longest identical substrings starting at these two indices. The LCE problem asks to preprocess a…
Binary Jumbled Pattern Matching via All-Pairs Shortest Paths
Danny Hermelin, Gad M. Landau, Yuri Rabinovich +1
In binary jumbled pattern matching we wish to preprocess a binary string in order to answer queries which ask for a substring of that is of size and has exactly…
Tree Compression with Top Trees
Philip Bille, Inge Li Goertz, Gad M. Landau +1
We introduce a new compression scheme for labeled trees based on top trees. Our compression scheme is the first to simultaneously take advantage of internal repeats in the tree (as…
Binary Jumbled Pattern Matching on Trees and Tree-Like Structures
Travis Gagie, Danny Hermelin, Gad M. Landau +1
Binary jumbled pattern matching asks to preprocess a binary string in order to answer queries which ask for a substring of that is of length and has exactly …
On Approximating String Selection Problems with Outliers
Christina Boucher, Gad M. Landau, Avivit Levy +2
Many problems in bioinformatics are about finding strings that approximately represent a collection of given strings. We look at more general problems where some input strings can…
Unified Compression-Based Acceleration of Edit-Distance Computation
Danny Hermelin, Gad M. Landau, Shir Landau +1
The edit distance problem is a classical fundamental problem in computer science in general, and in combinatorial pattern matching in particular. The standard dynamic programming s…
Random Access to Grammar Compressed Strings
Philip Bille, Gad M. Landau, Rajeev Raman +3
Grammar based compression, where one replaces a long string by a small context-free grammar that generates the string, is a simple and powerful paradigm that captures many popular…
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…