Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en I, Tomohiro; Kärkkäinen, Juha; Kempa, Dominik http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-44738
URL:

; ;

Faster Sparse Suffix Sorting

pdf-format:


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 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.

BibTeX - Entry

@InProceedings{i_et_al:LIPIcs:2014:4473,
  author =	{Tomohiro I and Juha K{\"a}rkk{\"a}inen and Dominik Kempa},
  title =	{{Faster Sparse Suffix Sorting}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{386--396},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Ernst W. Mayr and Natacha Portier},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4473},
  URN =		{urn:nbn:de:0030-drops-44738},
  doi =		{10.4230/LIPIcs.STACS.2014.386},
  annote =	{Keywords: string algorithms, sparse suffix sorting, sparse suffix trees, Karp-Rabin fingerprints, space-time tradeoffs}
}

Keywords: string algorithms, sparse suffix sorting, sparse suffix trees, Karp-Rabin fingerprints, space-time tradeoffs
Seminar: 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)
Issue date: 2014
Date of publication: 2014


DROPS-Home | Fulltext Search | Imprint Published by LZI