Module suffix_array 

Suffix array + LCP construction.

The C++ library has its own CaPS algorithm (a parallel SA construction). We build the suffix array in linear time with cdivsufsort (a byte-level divsufsort) and compute LCP with Kasai’s algorithm. The suffix array of a string is unique, so this produces the same order as a comparison sort would — bit-identical downstream results — but in O(n) instead of O(n² log n).

Structs

SuffixArray

Suffix array + LCP array for a text of length n.

Functions

build

Convenience: build both SA and LCP in one go.

build_lcp

Kasai’s algorithm — computes the LCP array from a text and its suffix array.

build_suffix_array

Build a suffix array for the given text.