### Minimal Suffix and Rotation of a Substring in Optimal Time

**2016-01-29**

1601.08051 | cs.DS

For a text given in advance, the substring minimal suffix queries ask to
determine the lexicographically minimal non-empty suffix of a substring
specified by the location of its occurrence in the text. We develop a data
structure answering such queries optimally: in constant time after linear-time
preprocessing. This improves upon the results of Babenko et al. (CPM 2014),
whose trade-off solution is characterized by $\Theta(n\log n)$ product of these
time complexities. Next, we extend our queries to support concatenations of
$O(1)$ substrings, for which the construction and query time is preserved. We
apply these generalized queries to compute lexicographically minimal and
maximal rotations of a given substring in constant time after linear-time
preprocessing.
Our data structures mainly rely on properties of Lyndon words and Lyndon
factorizations. We combine them with further algorithmic and combinatorial
tools, such as fusion trees and the notion of order isomorphism of strings.

**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-09-27**

1809.10531 | cs.CG

In the range closest pair problem, we want to construct a data structure
storing a set $S$ of $n$ po… 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

**2019-02-25**

1902.09228 | cs.DS

We consider the problem of designing succinct data structures for interval
graphs with $n$ vertices … 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-08-12**

1808.03978 | cs.DS

The Burrows-Wheeler Transform (BWT) is among the most influential discoveries
in text compression an… show more

**2018-09-14**

1809.05419 | cs.DS

Indexing of static and dynamic sets is fundamental to a large set of
applications such as informatio… show more

**2018-11-03**

1811.01209 | cs.DS

We study the problem of supporting queries on a string $S$ of length $n$
within a space bounded by t… 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-12-21**

1812.09120 | cs.DS

In this paper we study lower bounds for the fundamental problem of text
indexing with mismatches and… 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

**2018-01-23**

1801.07449 | cs.DS

We consider a sliding window $W$ over a stream of characters from some
alphabet of constant size. Th… 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