Space-time trade-offs for the shortest unique substring problem

DOI10.4230/LIPICS.ISAAC.2016.34MaRDI QIDQ4636517zbMATH OpenOpenAlexFDO

Authors Arnab Ganguly, Wing-Kai Hon, Rahul Shah, Sharma V. Thankachan

Publication date 19 April 2018

Full work available at URL https://doi.org/10.4230/LIPIcs.ISAAC.2016.34

zbMATH Keywords

probabilistic \(z\)-fast trieRabin-Karp fingerprintsparsificationsuccinct data structuressuffix tree

Mathematics Subject Classification ID

Data structures (68P05) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Algorithms on strings (68W32)

Recommendations

• Space-time trade-offs for finding shortest unique substrings and maximal unique matches
• A simple yet time-optimal and linear-space algorithm for shortest unique substring queries
• Shortest unique substrings queries in optimal time
• Space-efficient algorithms for computing minimal/shortest unique substrings
• Shortest unique substring query revisited

Cited in

(9)

• Two time-space tradeoffs for element distinctness
• Space-time trade-offs for finding shortest unique substrings and maximal unique matches
• Shortest unique substrings queries in optimal time
• Minimum unique substrings and maximum repeats
• A general Sequential Time-Space Tradeoff for Finding Unique Elements
• scientific article; zbMATH DE number 2087050 (Why is no real title available?)
• A simple yet time-optimal and linear-space algorithm for shortest unique substring queries
• Tight bounds on the maximum number of shortest unique substrings
• Range shortest unique substring queries

This page was built for publication: Space-time trade-offs for the shortest unique substring problem

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