Suffix Array and LCP Array
Last Updated: May 30, 2026
A suffix array is the lexicographically sorted order of every suffix of a string. The LCP (longest common prefix) array sits alongside it and records, for every pair of adjacent suffixes in the sorted order, how many characters they share at the start.
Together they form one of the most useful preprocessing structures in string algorithms. With a suffix array and LCP array you can:
- Pattern-match in O(m log n) per query after one-time O(n log n) preprocessing.
- Find the longest repeated substring in O(n).
- Count distinct substrings in O(n).
- Find the longest common substring of two or more strings in O(n).
- Replace many uses of suffix trees with a structure that takes half the memory.
This chapter covers the definition, a practical O(n log^2 n) construction algorithm, Kasai's O(n) LCP construction, and the most common applications.