52 citations · 133 across the 25 of their papers we have counts for
3 papers · 1 filter
Wavelet Trees Meet Suffix Trees
Maxim Babenko, Paweł Gawrychowski, Tomasz Kociumaka +1
We present an improved wavelet tree construction algorithm and discuss its applications to a number of rank/select problems for integer keys and strings. Given a string of length n…
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?",…