# sacapart

Computing the suffix array (the lexicographic order of all suffixes of a
text) is expensive, especially as the text gets large.

Sometimes, for very large inputs, a compromise is possible. Instead of
computing the suffix array of the *whole text*, we can compute the suffix
array of the first half, and the suffix array of the second half.

Memory usage remains roughly the same (depending on the SACA used), lookup
time gets worse by a constant factor (the number of partitions), and, across
partitions boundaries, worse (shorter) matches are sometimes found.

For some applications, like diffing very large files, this compromise makes
sense. Read the docs and the tests to see if `sacapart` is right for you.

Note: `sacapart` is meant to be used in conjuction with a SACA that supports
`sacabase`, like `divsufsort`.