文章基本信息

标题：Faster Sparse Suffix Sorting
本地全文：下载
作者：Tomohiro I ; Juha K{\"a}rkk{\"a}inen ; Dominik Kempa 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2014
卷号：25
页码：386-396
DOI：10.4230/LIPIcs.STACS.2014.386
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：string algorithms; sparse suffix sorting; sparse suffix trees; Karp-Rabin fingerprints; space-time tradeoffs