7 citations · 26 across the 14 of their papers we have counts for
4 papers · 1 filter
Time-Space Trade-Offs for Longest Common Extensions
Philip Bille, Inge Li Goertz, Benjamin Sach +1
We revisit the longest common extension (LCE) problem, that is, preprocess a string into a compact data structure that supports fast LCE queries. An LCE query takes a pair $(i,…
Sparse Suffix Tree Construction with Small Space
Philip Bille, Inge Li Gørtz, Tsvi Kopelowitz +2
We consider the problem of constructing a sparse suffix tree (or suffix array) for suffixes of a given text of size , using only words of space during constructio…
Tight Cell-Probe Bounds for Online Hamming Distance Computation
Raphael Clifford, Markus Jalsenius, Benjamin Sach
We show tight bounds for online Hamming distance computation in the cell-probe model with word size w. The task is to output the Hamming distance between a fixed string of length n…
Pattern Matching in Multiple Streams
Raphael Clifford, Markus Jalsenius, Ely Porat +1
We investigate the problem of deterministic pattern matching in multiple streams. In this model, one symbol arrives at a time and is associated with one of s streaming texts. The t…