Minimal suffix and rotation of a substring in optimal time

DOI10.4230/LIPICS.CPM.2016.28MaRDI QIDQ5369563zbMATH OpenOpenAlexFDO

Authors Tomasz Kociumaka

Publication date 17 October 2017

Full work available at URL https://arxiv.org/abs/1601.08051

zbMATH Keywords

Lyndon factorizationminimal rotationminimal suffixsubstring canonizationsubstring queries

Mathematics Subject Classification ID

Data structures (68P05) Combinatorics on words (68R15) Algorithms on strings (68W32)

Abstract: 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(nlogn)$ 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.

Recommendations

• Computing minimal and maximal suffixes of a substring
• Computing minimal and maximal suffixes of a substring revisited
• On minimal and maximal suffixes of a substring
• Optimal canonization of all substrings of a string
• Fast parallel Lyndon factorization with applications

Cited in

(14)

• Optimal canonization of all substrings of a string
• Dynamic and internal longest common substring
• Internal shortest absent word queries in constant time and linear space
• Computing minimal and maximal suffixes of a substring
• On minimal and maximal suffixes of a substring
• Lyndon factorization of grammar compressed texts revisited
• Computing minimal and maximal suffixes of a substring revisited
• Efficient enumeration of non-equivalent squares in partial words with few holes
• Near-optimal quantum algorithms for string problems
• On longest common property preserved substring queries
• Internal pattern matching queries in a text and applications
• An almost optimal edit distance oracle
• Sorted consecutive occurrence queries in substrings
• Counting distinct square substrings in sublinear time

This page was built for publication: Minimal suffix and rotation of a substring in optimal time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5369563)