2026-07-22T12:14:13Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4473 2024-03-06T10:35:06Z ddc:004 open_access

Faster Sparse Suffix Sorting I, Tomohiro Kärkkäinen, Juha Kempa, Dominik string algorithms sparse suffix sorting sparse suffix trees Karp-Rabin fingerprints space-time tradeoffs The sparse suffix sorting problem is to sort b=o(n) arbitrary suffixes of a string of length n using o(n) words of space in addition to the string. We present an O(n) time Monte Carlo algorithm using O(b.log(b)) space and an O(n.log(b)) time Las Vegas algorithm using O(b) space. This is a significant improvement over the best prior solutions of [Bille et al., ICALP 2013]: a Monte Carlo algorithm running in O(n.log(b)) time and O(b^(1+e)) space or O(n.log^2(b)) time and O(b) space, and a Las Vegas algorithm running in O(n.log^2(b)+b^2.log(b)) time and O(b) space. All the above results are obtained with high probability not just in expectation. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tomohiro I and Juha Kärkkäinen and Dominik Kempa 2014 Is Part Of LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2014.386 urn:nbn:de:0030-drops-44738 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.386 eng https://creativecommons.org/licenses/by/3.0/legalcode