Minimal suffix and rotation of a substring in optimal time

DOI10.4230/LIPICS.CPM.2016.28zbMATH Open1380.68151arXiv1601.08051OpenAlexW2963919504MaRDI QIDQ5369563FDOQ5369563

Authors: Tomasz Kociumaka 

Publication date: 17 October 2017

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.

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

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

zbMATH Keywords

minimal suffixsubstring queriesLyndon factorizationminimal rotationsubstring canonization

Mathematics Subject Classification ID

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

Cited In (11)

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

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)