39 citations · 255 across the 76 of their papers we have counts for
10 papers · 1 filter
Queries on LZ-Bounded Encodings
Djamal Belazzougui, Travis Gagie, Paweł Gawrychowski +4
We describe a data structure that stores a string in space similar to that of its Lempel-Ziv encoding and efficiently supports access, rank and select queries. These queries ar…
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…
Optimal Encodings for Range Top-k, Selection, and Min-Max
Pawel Gawrychowski, Patrick K. Nicholson
We consider encoding problems for range queries on arrays. In these problems the goal is to store a structure capable of recovering the answer to all queries that occupies the info…
Tight tradeoffs for approximating palindromes in streams
Paweł Gawrychowski, Przemysław Uznański
We consider computing the longest palindrome in a text of length in the streaming model, where the characters arrive one-by-one, and we do not have random access to the input.…
Encodings of Range Maximum-Sum Segment Queries and Applications
Pawel Gawrychowski, Patrick K. Nicholson
Given an array A containing arbitrary (positive and negative) numbers, we consider the problem of supporting range maximum-sum segment queries on A: i.e., given an arbitrary range…
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…