Space-Time Trade-Offs for the Shortest Unique Substring Problem.

DOI10.4230/LIPICS.ISAAC.2016.34zbMATH Open1398.68704OpenAlexW2575505998MaRDI QIDQ4636517

Wing-Kai Hon, Arnab Ganguly, 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

suffix treesparsificationsuccinct data structuresRabin-Karp fingerprintprobabilistic \(z\)-fast trie

Mathematics Subject Classification ID

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

Related Items (5)

Two time-space tradeoffs for element distinctness ⋮ In-place algorithms for exact and approximate shortest unique substring problems ⋮ A general Sequential Time-Space Tradeoff for Finding Unique Elements ⋮ Range shortest unique substring queries ⋮ Tight bounds on the maximum number of shortest unique substrings

This page was built for publication: Space-Time Trade-Offs for the Shortest Unique Substring Problem.