Suffix Array and LCP Array from Scratch (2026)
A suffix array is a sorted array of all suffixes of a string, typically constructed in O(n log n) or O(n) time. Combined with the Longest Common Prefix (LCP) array, it enables efficient string processing: substring search, longest repeated substring, and pattern matching.
LCP[i] stores the longest common prefix between suffix array positions i and i-1. Together, suffix and LCP arrays solve many string problems that would otherwise require suffix trees.
Suffix Array Construction
The suffix array is built by sorting suffixes lexicographically. The O(n log n) approach uses counting sort on ranks that are iteratively doubled. O(n) construction using SA-IS or DC3 is possible but more complex.
Each suffix is represented by its starting index. For string 'banana', suffixes are 'banana', 'anana', 'nana', 'ana', 'na', 'a', which sort to ['a', 'ana', 'anana', 'banana', 'na', 'nana'] with indices [5, 3, 1, 0, 4, 2].
vector buildSuffixArray(string s) {
s += '$';
int n = s.size();
vector sa(n), rank(n), tmp(n);
for (int i = 0; i < n; i++) sa[i] = i, rank[i] = s[i];
for (int k = 1; k < n; k *= 2) {
auto cmp = [&](int a, int b) {
if (rank[a] != rank[b]) return rank[a] < rank[b];
int ra = a + k < n ? rank[a + k] : -1;
int rb = b + k < n ? rank[b + k] : -1;
return ra < rb;
};
sort(sa.begin(), sa.end(), cmp);
tmp[sa[0]] = 0;
for (int i = 1; i < n; i++)
tmp[sa[i]] = tmp[sa[i-1]] + cmp(sa[i-1], sa[i]);
rank = tmp;
if (rank[sa.back()] == n - 1) break;
}
sa.erase(sa.begin()); // remove sentinel
return sa;
} LCP Array Construction (Kasai's Algorithm)
Kasai's algorithm computes the LCP array in O(n) time using inverse suffix array ranks. It processes suffixes in original order (not sorted), maintaining the current LCP length k. For each adjacent suffix pair in the suffix array, characters are compared starting from k.
The LCP array enables substring search in O(m log n), and with RMQ preprocessing, longest common prefix queries between any two suffixes are answered in O(1).
vector buildLCPArray(string& s, vector& sa) {
int n = sa.size();
vector rank(n), lcp(n, 0);
for (int i = 0; i < n; i++) rank[sa[i]] = i;
int k = 0;
for (int i = 0; i < n; i++) {
if (rank[i] == 0) { k = 0; continue; }
int j = sa[rank[i] - 1];
while (i + k < n && j + k < n && s[i + k] == s[j + k]) k++;
lcp[rank[i]] = k;
if (k) k--;
}
return lcp;
} Frequently Asked Questions
What is the LCP array used for?
LCP array enables finding the longest repeated substring (maximum LCP value), counting distinct substrings (sum of n - sa[i] - lcp[i]), and pattern matching in O(m log n) time via binary search on the suffix array.
How do suffix array and suffix tree compare?
Suffix arrays use less memory (O(n) integers vs O(n) nodes with pointers) and are cache-friendlier. Suffix trees support O(m) pattern matching without binary search. Both are interconvertible via LCP and stack-based algorithms.
Originally published on Ayodhyyya. Last updated June 1, 2026.