ML p(r)ior | Minimal Suffix and Rotation of a Substring in Optimal Time

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.
PDF

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

2019-02-14
1902.05224 | cs.DS

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

Highlights - Most important sentences from the article

2019-01-30

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

Highlights - Most important sentences from the article

2019-02-25

We consider the problem of designing succinct data structures for interval graphs with $n$ vertices … show more
PDF

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

2018-09-08

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

Highlights - Most important sentences from the article

2018-08-12
1808.03978 | cs.DS

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

Highlights - Most important sentences from the article

2018-09-14

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

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

2017-12-22

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

Highlights - Most important sentences from the article

2018-12-21

In this paper we study lower bounds for the fundamental problem of text indexing with mismatches and… show more
PDF

Highlights - Most important sentences from the article

2018-04-23

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

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

2019-01-30

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

Highlights - Most important sentences from the article