Dismantling DivSufSort

2017/10/05 by Fischer, Johannes, Kurpicz, Florian
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1710.01896

Abstract

We give the first concise description of the fastest known suffix sorting algorithm in main memory, the DivSufSort by Yuta Mori. We then present an extension that also computes the LCP-array, which is competitive with the fastest known LCP-array construction algorithm.

Related

• Inducing the LCP-Array
• Fast and Lightweight Distributed Suffix Array Construction -- First Results
• Sparse Suffix and LCP Array: Simple, Direct, Small, and Fast
• On the Optimisation of the GSACA Suffix Array Construction Algorithm
• Lightweight LCP-Array Construction in Linear Time