Computing minimal and maximal suffixes of a substring

DOI10.1016/J.TCS.2015.08.023MaRDI QIDQ294952zbMATH OpenOpenAlexFDO

Authors Paweł Gawrychowski, Tomasz Kociumaka, Ignat Kolesnichenko, Tatiana Starikovskaya, Maxim Babenko

Publication date 16 June 2016

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2015.08.023

zbMATH Keywords

data structureslexicographic ordermaximal suffixminimal suffixsubstring queries

Mathematics Subject Classification ID

Data structures (68P05) Algorithms on strings (68W32)

Recommendations

• Computing minimal and maximal suffixes of a substring revisited
• On minimal and maximal suffixes of a substring
• Minimal suffix and rotation of a substring in optimal time
• Linear-size suffix tries
• Generalized substring compression

Cites work

• scientific article; zbMATH DE number 1512678 (Why is no real title available?)
• scientific article; zbMATH DE number 1786458 (Why is no real title available?)
• Algorithms on Strings
• Extracting powers and periods in a word from its runs structure
• Factorizing words over an ordered alphabet
• Faster range LCP queries
• Free differential calculus. IV: The quotient groups of the lower central series
• Generalized substring compression
• Internal pattern matching queries in a text and applications
• Range LCP
• Simple real-time constant-space string matching
• Substring compression problems
• Surpassing the information theoretic bound with fusion trees
• Uniqueness Theorems for Periodic Functions
• Wavelet trees meet suffix trees

Cited in

(7)

• Finding the maximum suffix with fewer comparisons
• On minimal and maximal suffixes of a substring
• Near-optimal quantum algorithms for string problems
• Finding the maximum suffix with fewer comparisons
• Internal shortest absent word queries in constant time and linear space
• Minimal suffix and rotation of a substring in optimal time
• Computing minimal and maximal suffixes of a substring revisited

This page was built for publication: Computing minimal and maximal suffixes of a substring

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