Florian Kurpicz

LCP Array Construction

The suffix array is often accompanied by the longest common prefix (LCP) array. We present a new LCP array construction algorithm and provide an extensive benchmark for all LCP array construction algorithms that we are aware of.

Our LCP array construction algorithm extends DivSufSort, which is the fastest main memory suffix sorting algorithm (in practice). It uses techniques that are similar to the LCP array construction algorithm based on SAIS (https://github.com/kurpicz/sais-lite-lcp/). However, it is faster due to the faster suffix array construction.

Implementations

Our new LCP array construction algorithm is available at https://github.com/kurpicz/libdivsufsort/. Additionally, there is a small benchmark tool that allows to compare all main memory LCP array construction algorithms that we are aware of. This tool is available at https://github.com/kurpicz/lcp-test/.

Posts Related to LCP Array Construction

Presentation at PSC 2017
2017-08-31

Dismantling DivSufSort