Suffix Arrays & Trees
A suffix array is a sorted array of all suffixes of a string. It is the Swiss Army knife of string algorithms — once you have it (plus its companion the LCP array), you can answer questions about repeated substrings, longest common substrings, and distinct substrings in near-linear time.
What Is a Suffix?
For string s = "banana", the suffixes are all substrings starting at each index:
Index Suffix 0 banana 1 anana 2 nana 3 ana 4 na 5 a Sorted suffixes: 5 a 3 ana 1 anana 0 banana 4 na 2 nana Suffix Array SA = [5, 3, 1, 0, 4, 2]
Naive Construction — O(n² log n)
The simplest approach: generate all n suffixes, sort them lexicographically. Each string comparison costs O(n), sorting costs O(n log n) comparisons → O(n² log n) total.
// Naive suffix array — O(n^2 log n)
function buildSuffixArrayNaive(s: string): number[] {
const n = s.length;
const indices = Array.from({ length: n }, (_, i) => i);
// Sort indices by their corresponding suffix
indices.sort((a, b) => {
const sa = s.slice(a);
const sb = s.slice(b);
return sa < sb ? -1 : sa > sb ? 1 : 0;
});
return indices;
}
const sa = buildSuffixArrayNaive("banana");
console.log(sa); // [5, 3, 1, 0, 4, 2]
// Get sorted suffixes for visual inspection
function getSortedSuffixes(s: string, sa: number[]): string[] {
return sa.map(i => s.slice(i));
}
console.log(getSortedSuffixes("banana", sa));
// ["a", "ana", "anana", "banana", "na", "nana"]O(n log n) Construction — Prefix Doubling
The prefix doubling algorithm sorts suffixes in O(n log n) by iteratively sorting on lengths 1, 2, 4, 8, … doubling the comparison window each pass. After at most log n passes, all suffix ranks are unique.
// O(n log n) suffix array via prefix doubling (DC3 / SA-IS give O(n) but are complex)
function buildSuffixArray(s: string): number[] {
const n = s.length;
let sa = Array.from({ length: n }, (_, i) => i);
let rank = Array.from(s, c => c.charCodeAt(0));
const tmp = new Array(n);
for (let gap = 1; gap < n; gap *= 2) {
const rankCopy = rank.slice();
const compare = (a: number, b: number): number => {
if (rankCopy[a] !== rankCopy[b]) return rankCopy[a] - rankCopy[b];
const ra = a + gap < n ? rankCopy[a + gap] : -1;
const rb = b + gap < n ? rankCopy[b + gap] : -1;
return ra - rb;
};
sa.sort(compare);
// Reassign ranks based on new sorted order
tmp[sa[0]] = 0;
for (let i = 1; i < n; i++) {
tmp[sa[i]] = tmp[sa[i - 1]] + (compare(sa[i], sa[i - 1]) !== 0 ? 1 : 0);
}
rank = tmp.slice();
if (rank[sa[n - 1]] === n - 1) break; // all ranks unique — done
}
return sa;
}
console.log(buildSuffixArray("banana")); // [5, 3, 1, 0, 4, 2]LCP Array — Longest Common Prefix
The LCP array stores the length of the longest common prefix between consecutive entries in the suffix array: LCP[i] = lcp(sa[i-1], sa[i]). Kasai's algorithm builds it in O(n) using the insight that LCP values can only decrease by 1 between adjacent positions in the original string.
// Kasai's algorithm — O(n) LCP array
function buildLCP(s: string, sa: number[]): number[] {
const n = s.length;
const rank = new Array(n);
for (let i = 0; i < n; i++) rank[sa[i]] = i; // inverse suffix array
const lcp = new Array(n).fill(0);
let h = 0; // current lcp height
for (let i = 0; i < n; i++) {
if (rank[i] > 0) {
const j = sa[rank[i] - 1]; // previous suffix in sorted order
while (i + h < n && j + h < n && s[i + h] === s[j + h]) h++;
lcp[rank[i]] = h;
if (h > 0) h--; // LCP can drop by at most 1
}
}
return lcp;
}
// "banana": SA = [5,3,1,0,4,2], suffixes = ["a","ana","anana","banana","na","nana"]
// LCP between consecutive sorted suffixes:
// lcp("a","ana") = 1 ("a")
// lcp("ana","anana")= 3 ("ana")
// lcp("anana","banana") = 0
// lcp("banana","na") = 0
// lcp("na","nana") = 2 ("na")
const sa2 = buildSuffixArray("banana");
console.log(buildLCP("banana", sa2)); // [0, 1, 3, 0, 0, 2]Longest Repeated Substring
The longest repeated substring equals the maximum value in the LCP array. The LCP[i] value tells you that suffixes sa[i-1] and sa[i] share their first LCP[i] characters.
function longestRepeatedSubstring(s: string): string {
const sa = buildSuffixArray(s);
const lcp = buildLCP(s, sa);
let maxLen = 0, maxIdx = 0;
for (let i = 1; i < lcp.length; i++) {
if (lcp[i] > maxLen) { maxLen = lcp[i]; maxIdx = sa[i]; }
}
return s.slice(maxIdx, maxIdx + maxLen);
}
console.log(longestRepeatedSubstring("banana")); // "ana"
console.log(longestRepeatedSubstring("abcabcabc")); // "abcabc"Longest Common Substring of Two Strings
Concatenate both strings with a sentinel separator character that does not appear in either string (e.g. "#" with char code 0). Build the suffix array of the combined string. The longest common substring is the maximum LCP value between two adjacent suffixes from different original strings.
function longestCommonSubstring(a: string, b: string): string {
const sep = String.fromCharCode(0); // sentinel — lexicographically smallest
const s = a + sep + b;
const na = a.length;
const sa = buildSuffixArray(s);
const lcp = buildLCP(s, sa);
let maxLen = 0, maxIdx = 0;
for (let i = 1; i < sa.length; i++) {
// One suffix must come from 'a' and the other from 'b'
const fromA = (sa[i - 1] < na) !== (sa[i] < na);
if (fromA && lcp[i] > maxLen) {
maxLen = lcp[i];
maxIdx = sa[i] < na ? sa[i] : sa[i - 1];
}
}
return a.slice(maxIdx, maxIdx + maxLen);
}
console.log(longestCommonSubstring("abcdef", "cdefgh")); // "cdef"Count Distinct Substrings
Total substrings of a string of length n = n(n+1)/2. Subtracting the sum of all LCP values removes duplicates, since each duplicate is counted by its LCP value.
distinct substrings = n(n+1)/2 − sum(LCP)
function countDistinctSubstrings(s: string): number {
const n = s.length;
const sa = buildSuffixArray(s);
const lcp = buildLCP(s, sa);
const total = (n * (n + 1)) / 2;
const duplicates = lcp.reduce((a, b) => a + b, 0);
return total - duplicates;
}
console.log(countDistinctSubstrings("banana")); // 15
// Total = 6*7/2 = 21, LCP sum = 0+1+3+0+0+2 = 6, distinct = 21-6 = 15Suffix Automaton — Brief Introduction
A suffix automaton (SAM) is a minimal directed acyclic word graph (DAWG) that represents all substrings of a string. It has O(n) nodes and O(n) transitions, making it the most space-efficient representation.
Key properties:
Accepts all suffixes of the original string
Has O(n) states and O(n) transitions for a string of length n
Can answer "does substring t appear in s?" in O(|t|) time
Used for: counting distinct substrings, finding occurrences, longest common substring
More complex to implement than suffix array but has better constant factors
Comparison
Structure | Build time | Space | Best for |
|---|---|---|---|
Suffix Array (naive) | O(n² log n) | O(n) | Simple implementation, small strings |
Suffix Array (doubling) | O(n log n) | O(n) | Most competitive programming tasks |
Suffix Array (SA-IS) | O(n) | O(n) | Production systems, very long strings |
Suffix Tree | O(n) | O(n) | Complex queries, substring matching |
Suffix Automaton | O(n) | O(n) | Distinct substrings, all occurrences |