Sparse Suffix and LCP Array: Simple, Direct, Small, and Fast

Lorraine A. K. Ayad, Grigorios Loukides, Solon P. Pissis +1

Sparse suffix sorting is the problem of sorting $b=o(n)$ suffixes of a string of length $n$. Efficient sparse suffix sorting algorithms have existed for more than a decade. Despite…