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 √ 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 ≤ n is the nu...

Full description

Saved in:
Bibliographic Details
Published in:ACM transactions on algorithms 2020-09, Vol.16 (4), p.1-53
Main Authors: Fischer, Johannes, I, Tomohiro, Köppl, Dominik
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
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 √ 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 ≤ n is the number of suffixes to be sorted (provided online and arbitrarily), and c is the number of characters with m ≤ c ≤ n that must be compared for distinguishing the designated suffixes.
ISSN:1549-6325
1549-6333
DOI:10.1145/3398681