the LCP array
A suffix array lists all suffixes in sorted order, but it tells you nothing about how similar neighboring suffixes are. The LCP array fills that gap. For each pair of suffixes that are adjacent in the sorted order, it records how many characters they share at the start — their longest common prefix. This single companion array is what unlocks the full power of a suffix array, letting it match a suffix tree feature for feature.
Formally, given a string S and its suffix array SA, the LCP array stores LCP[i] = the length of the longest common prefix of the suffix at SA[i] and the suffix at SA[i-1] (the one just before it in sorted order). For "banana" with SA = [5,3,1,0,4,2] giving sorted suffixes a, ana, anana, banana, na, nana, the LCP array is [-, 1, 3, 0, 0, 2]: "ana" and "anana" share "ana" (3), "na" and "nana" share "na" (2), and so on. There is a slick way to compute it: Kasai's algorithm builds the LCP array in O(n) time using the suffix array and its inverse, by scanning suffixes in original-string order and observing that the LCP value can drop by at most one as you move to the next-shorter suffix, so total work is linear. Range-minimum queries over the LCP array then give the longest common prefix of any two suffixes, not just adjacent ones.
Why it matters: the LCP array is the bridge from a flat suffix array to suffix-tree-level queries. The smallest LCP value in a range equals the string-depth of the corresponding internal node of the suffix tree, so the maximum LCP value is the length of the longest repeated substring; summing n - SA[i] - LCP[i] counts distinct substrings; and LCP information sharpens pattern search from O(m log n) toward O(m + log n). In short, suffix array plus LCP array is the practical, memory-light substitute for a suffix tree — and the LCP array is the part that supplies the 'how much do these suffixes overlap' knowledge a bare sorted list lacks.
Sorted suffixes of "banana": a, ana, anana, banana, na, nana with LCP = [-, 1, 3, 0, 0, 2]. The maximum value, 3, says the longest repeated substring has length 3 — and indeed "ana" repeats. The zeros at the 'banana' and 'na' boundaries mark places where neighboring suffixes share nothing, i.e. branch points in the implied suffix tree.
LCP[i] = overlap of adjacent sorted suffixes; its maximum is the longest repeated substring length.
The LCP array is meaningless without the suffix array it accompanies — it indexes adjacency in sorted order, not original positions. Kasai's O(n) construction is the standard; computing LCPs by brute-force comparison would cost O(n^2).