35 citations · 50 across the 10 of their papers we have counts for
10 papers · 1 filter
Time-Space Trade-Offs for Lempel-Ziv Compressed Indexing
Philip Bille, Mikko Berggren Ettienne, Inge Li Gørtz +1
Given a string , the \emph{compressed indexing problem} is to preprocess into a compressed representation that supports fast \emph{substring queries}. The goal is to use lit…
Longest Common Extensions in Sublinear Space
Philip Bille, Inge Li Gørtz, Mathias Bæk Tejs Knudsen +2
The longest common extension problem (LCE problem) is to construct a data structure for an input string of length that supports LCE queries. Such a query returns the…
Dynamic Relative Compression, Dynamic Partial Sums, and Substring Concatenation
Philip Bille, Patrick Hagge Cording, Inge Li Gørtz +3
Given a static reference string and a source string , a relative compression of with respect to is an encoding of as a sequence of references to substrings of $R…
Sublinear Space Algorithms for the Longest Common Substring Problem
Tomasz Kociumaka, Tatiana Starikovskaya, Hjalte Wedel Vildhøj
Given documents of total length , we consider the problem of finding a longest string common to at least of the documents. This problem is known as the \emph{long…
A Suffix Tree Or Not A Suffix Tree?
Tatiana Starikovskaya, Hjalte Wedel Vildhøj
In this paper we study the structure of suffix trees. Given an unlabeled tree on nodes and suffix links of its internal nodes, we ask the question "Is a suffix tree?",…
Fingerprints in Compressed Strings
Philip Bille, Patrick Hagge Cording, Inge Li Gørtz +3
The Karp-Rabin fingerprint of a string is a type of hash value that due to its strong properties has been used in many string algorithms. In this paper we show how to construct a d…
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…
String Matching with Variable Length Gaps
Philip Bille, Inge Li Goertz, Hjalte Wedel Vildhøj +1
We consider string matching with variable length gaps. Given a string and a pattern consisting of strings separated by variable length gaps (arbitrary strings of length in…
String Indexing for Patterns with Wildcards
Philip Bille, Inge Li Goertz, Hjalte Wedel Vildhøj +1
We consider the problem of indexing a string of length to report the occurrences of a query pattern containing characters and wildcards. Let be the number…