### Deterministic sub-linear space LCE data structures with efficient construction

**2016-01-28**

1601.07670 | cs.DS

Given a string $S$ of $n$ symbols, a longest common extension query
$\mathsf{LCE}(i,j)$ asks for the length of the longest common prefix of the
$i$th and $j$th suffixes of $S$. LCE queries have several important
applications in string processing, perhaps most notably to suffix sorting.
Recently, Bille et al. (J. Discrete Algorithms 25:42-50, 2014, Proc. CPM 2015:
65-76) described several data structures for answering LCE queries that offers
a space-time trade-off between data structure size and query time. In
particular, for a parameter $1 \leq \tau \leq n$, their best deterministic
solution is a data structure of size $O(n/\tau)$ which allows LCE queries to be
answered in $O(\tau)$ time. However, the construction time for all
deterministic versions of their data structure is quadratic in $n$. In this
paper, we propose a deterministic solution that achieves a similar space-time
trade-off of $O(\tau\min\{\log\tau,\log\frac{n}{\tau}\})$ query time using
$O(n/\tau)$ space, but significantly improve the construction time to
$O(n\tau)$.

**Login to like/save this paper, take notes and configure your recommendations**

# Related Articles

**2017-12-13**

1712.04886 | cs.DS

We propose algorithms that, given the input string of length $n$ over integer
alphabet of size $\sig… show more

**2019-04-08**

1904.04228 | cs.DS

Burrows-Wheeler transform (BWT) is an invertible text transformation that,
given a text $T$ of lengt… show more

**2018-11-03**

1811.01248 | cs.DS

Given $d$ strings over the alphabet $\{0,1,\ldots,\sigma{-}1\}$, the
classical Aho--Corasick data st… show more

**2019-02-14**

1902.05224 | cs.DS

Converting a compressed format of a string into another compressed format
without an explicit decomp… show more

**2019-01-30**

1901.10722 | cs.DS

Palindromes are important objects in strings which have been extensively
studied from combinatorial,… show more

**2018-11-05**

1811.02078 | cs.DS

Given an $n$-bit array $A$, the succinct rank data structure problem asks to
construct a data struct… show more

**2018-12-02**

1812.00359 | cs.DS

We consider two closely related problems of text indexing in a sub-linear
working space. The first p… show more

**2018-09-08**

1809.02792 | cs.DS

Indexing highly repetitive texts --- such as genomic databases, software
repositories and versioned … show more

**2018-06-05**

1806.01804 | cs.DS

We present the first solution to $\tau$-majorities on tree paths. Given a
tree of $n$ nodes, each wi… show more

**2017-12-22**

1712.08573 | cs.DS

In the longest common substring problem, we are given two strings of length
$n$ and must find a subs… show more

**2018-04-23**

1804.08731 | cs.DS

In the longest common substring (LCS) problem, we are given two strings $S$
and $T$, each of length … show more

**2019-01-30**

1901.10633 | cs.DS

A maximal repetition, or run, in a string, is a periodically maximal
substring whose smallest period… show more

**2015-01-10**

1501.02309 | cs.CG

Given a set $P$ of $n$ uncertain points on the real line, each represented by
its one-dimensional pr… show more

**2018-06-26**

1806.09823 | cs.DS

The nearest neighbor problem is defined as follows: Given a set $P$ of $n$
points in some metric spa… show more

**2012-03-06**

1203.1080 | cs.CC

In this paper we investigate the problem of building a static data structure
that represents a strin… show more

**2013-07-25**

1307.6789 | cs.DS

Let $\mathcal{D}$ be a collection of $D$ documents, which are strings over an
alphabet of size $\sig… show more