@inproceedings{e4c26ab942624442964d001cfabe2b0b,
title = "Faster sparse suffix sorting",
abstract = "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 by Bille et al. (ICALP 2013): a Monte Carlo algorithm running in O(n log b) time and O(b1+ε) space or O(n log2b) time and O(b) space, and a Las Vegas algorithm running in O(n log2b+b2log b) time and O(b) space. All the above results are obtained with high probability not just in expectation.",
keywords = "Karp-Rabin fingerprints, Space-time tradeoffs, Sparse suffix sorting, Sparse suffix trees, String algorithms",
author = "Tomohiro I and Juha K{\"a}rkk{\"a}inen and Dominik Kempa",
note = "Publisher Copyright: {\textcopyright} Tomohiro I, Juha K{\"a}rkk{\"a}inen, and Dominik Kempa.; 31st International Symposium on Theoretical Aspects of Computer Science, STACS 2014 ; Conference date: 05-03-2014 Through 08-03-2014",
year = "2014",
month = mar,
day = "1",
doi = "10.4230/LIPIcs.STACS.2014.386",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
pages = "386--396",
editor = "Natacha Portier and Mayr, \{Ernst W.\}",
booktitle = "31st International Symposium on Theoretical Aspects of Computer Science, STACS 2014",
}