Deterministic Sparse Suffix Sorting in the Restore Model

Given a text \(T\) of length \(n\), we propose a deterministic online algorithm computing the sparse suffix array and the sparse longest common prefix array of \(T\) in \(O(c \sqrt{\lg n} + m \lg m \lg n \lg^* n)\) time with \(O(m)\) words of space under the premise that the space of \(T\) is rewrit...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2018-02
Main Authors: Fischer, Johannes, Tomohiro, I, Köppl, Dominik
Format: Article
Language:English
Subjects:
Algorithms
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Given a text \(T\) of length \(n\), we propose a deterministic online algorithm computing the sparse suffix array and the sparse longest common prefix array of \(T\) in \(O(c \sqrt{\lg n} + m \lg m \lg n \lg^* n)\) time with \(O(m)\) words of space under the premise that the space of \(T\) is rewritable, where \(m \le n\) is the number of suffixes to be sorted (provided online and arbitrarily), and \(c\) is the number of characters with \(m \le c \le n\) that must be compared for distinguishing the designated suffixes.
ISSN:2331-8422