A suffix array is the sorted list of every suffix of a string, represented compactly as start indices. Paired with the LCP array — the longest common prefix between adjacent suffixes — it powers substring search in O(m log n), longest-repeated-substring detection, distinct-substring counting, and full-text search. This builder shows every suffix in sorted order plus the running LCP, computed via Kasai's classic linear-time algorithm.
Sorting suffixes lexicographically clusters everything that shares a prefix into a contiguous slice of the array. To find whether a pattern P occurs in the text, two binary searches locate the first and last suffix whose sorted key is P… — that's O(m log n) comparisons. To count distinct substrings, notice that suffix i contributes n − SA[i] − LCP[i] new prefixes (the ones not already shared with its predecessor), summed across all rows. And the maximum LCP value is the length of the longest substring that appears at least twice, with the pair of positions read off from the two adjacent SA rows. Kasai's algorithm walks the text in original order and uses the inverse rank to bound how much LCP can shrink per step — amortised O(n). This builder uses the O(n log² n) prefix-doubling sort, which is fast enough for interactive text up to a few thousand characters.