Pattern Guide
Suffix Array & LCP Array
"Sort all suffixes. Build LCP array. Enables O(n log n) solutions for hard string problems."
A suffix array stores all suffixes of a string in sorted lexicographic order. Combined with the LCP (Longest Common Prefix) array — which stores the length of the longest common prefix between consecutive suffixes — it enables O(n log n) solutions for: longest repeated substring, number of distinct substrings, pattern matching, and longest common substring of multiple strings.
Problems you can solve with this pattern
4 problems · click any to start solving
// O(n log²n) suffix array construction
function buildSA(s) {
const n = s.length;
let sa = Array.from({length: n}, (_, i) => i);
let rank = [...s].map(c => c.charCodeAt(0));
let tmp = new Array(n);
for (let gap = 1; gap < n; gap <<= 1) {
const cmp = (a, b) => {
if (rank[a] !== rank[b]) return rank[a] - rank[b];
const ra = a + gap < n ? rank[a + gap] : -1;
const rb = b + gap < n ? rank[b + gap] : -1;
return ra - rb;
};
sa.sort(cmp);
tmp[sa[0]] = 0;
for (let i = 1; i < n; i++)
tmp[sa[i]] = tmp[sa[i-1]] + (cmp(sa[i-1], sa[i]) < 0 ? 1 : 0);
rank = [...tmp];
if (rank[sa[n-1]] === n-1) break;
}
return sa;
}
// Kasai's algorithm: build LCP array in O(n)
function buildLCP(s, sa) {
const n = s.length;
const rank = new Array(n);
for (let i = 0; i < n; i++) rank[sa[i]] = i;
const lcp = new Array(n).fill(0);
let h = 0;
for (let i = 0; i < n; i++) {
if (rank[i] > 0) {
let j = sa[rank[i] - 1];
while (i + h < n && j + h < n && s[i + h] === s[j + h]) h++;
lcp[rank[i]] = h;
if (h > 0) h--;
}
}
return lcp; // lcp[i] = LCP(sa[i-1], sa[i])
}
// Count distinct substrings = total substrings - sum(lcp)
// = n*(n+1)/2 - sum(lcp array)A suffix array SA[] is a sorted list of starting indices of all suffixes. For "banana": suffixes sorted = [a, ana, anana, banana, na, nana] → SA = [5,3,1,0,4,2]. The LCP array stores longest common prefix between SA[i] and SA[i-1] suffixes. Together they compress all substring information into two arrays, enabling many string operations in O(n) or O(n log n).
// O(n log²n) suffix array construction
function buildSA(s) {
const n = s.length;
let sa = Array.from({length: n}, (_, i) => i);
let rank = [...s].map(c => c.charCodeAt(0));
let tmp = new Array(n);
for (let gap = 1; gap < n; gap <<= 1) {
const cmp = (a, b) => {
if (rank[a] !== rank[b]) return rank[a] - rank[b];
const ra = a + gap < n ? rank[a + gap] : -1;
const rb = b + gap < n ? rank[b + gap] : -1;
return ra - rb;
};
sa.sort(cmp);
tmp[sa[0]] = 0;
for (let i = 1; i < n; i++)
tmp[sa[i]] = tmp[sa[i-1]] + (cmp(sa[i-1], sa[i]) < 0 ? 1 : 0);
rank = [...tmp];
if (rank[sa[n-1]] === n-1) break;
}
return sa;
}
// Kasai's algorithm: build LCP array in O(n)
function buildLCP(s, sa) {
const n = s.length;
const rank = new Array(n);
for (let i = 0; i < n; i++) rank[sa[i]] = i;
const lcp = new Array(n).fill(0);
let h = 0;
for (let i = 0; i < n; i++) {
if (rank[i] > 0) {
let j = sa[rank[i] - 1];
while (i + h < n && j + h < n && s[i + h] === s[j + h]) h++;
lcp[rank[i]] = h;
if (h > 0) h--;
}
}
return lcp; // lcp[i] = LCP(sa[i-1], sa[i])
}
// Count distinct substrings = total substrings - sum(lcp)
// = n*(n+1)/2 - sum(lcp array)- SA[i] = starting index of the i-th smallest suffix
- LCP[i] = length of longest common prefix between SA[i-1] and SA[i]
- Distinct substrings = n*(n+1)/2 - sum(LCP)
- Longest repeated substring = max(LCP)
- Pattern search: binary search in SA for pattern match range
Construction complexity:
- Naive sort: O(n² log n)
- O(n log²n): sort with doubled comparison
- O(n log n): radix sort variant (SA-IS: O(n))
vs Rolling Hash: Suffix array gives exact answers, no collision risk. Harder to code but more powerful for multi-query scenarios.