Deterministic Sparse Suffix Sorting on Rewritable Texts

Abstract

Given a rewriteable text $T$ of length $n$ on an alphabet of size $\sigma$, we propose an online algorithm that computes the sparse suffix array and the sparse longest common prefix array of $T$ in $\Oh{\abs{\Comlcp} \sqrt{\lg n} + m \lg m \lg n \lg^* n}$ time by using the text space and $\Oh{m}$ additional working space, where $m$ is the number of some positions $\Pos$ on $[1..n]$, provided online and arbitrarily, and $\Comlcp = \bigcup_{p,p' \in \Pos, p \neq p'} [p..p+\lcp(T[p..], T[p'..])]$.