Suffix Array
Rank suffixes by doubling prefix lengths until their lexicographic order becomes unique.
Core idea
The doubling algorithm ranks suffixes by prefixes of length 1, 2, 4, and so on. A longer rank is determined by the pair of ranks for its first and second halves.
Read the visualization
Each row lists a suffix index, its current rank pair, and its sorted position. Equal pairs share a new rank until enough characters distinguish every suffix.
b0
a1
n2
a3
n4
a5
Doubling length k = 1
StartSuffixrankKeys (first, second)
1anana0(0, 2)
3ana0(0, 2)
5a0(0, ∞)
0banana1(1, 0)
2nana2(2, 0)
4na2(2, 0)
Start with every text suffix and rank it by its first character.
1function suffixArray(s: string): number[] {
2 const n = s.length;
3 let rank = s.split('').map(c => c.charCodeAt(0)); // init rank = init character
4 let sa = [...Array(n).keys()];
5 const key = (i: number, k: number): [number, number] =>
6 [rank[i], i + k < n ? rank[i + k]: -1];
7 for (let k = 1;; k <<= 1) {
8 sa.sort((a, b) => { // sort (sort k digit, sort k digit) sort
9 const ka = key(a, k), kb = key(b, k);
10 return ka[0] - kb[0] || ka[1] - kb[1];
11 });
12 const nr = Array(n).fill(0);
13 for (let x = 1; x < n; x++) {
14 const kp = key(sa[x - 1], k), kq = key(sa[x], k);
15 nr[sa[x]] = nr[sa[x - 1]] + // duplicate rank 0 rank rank
16 (kp[0] !== kq[0] || kp[1] !== kq[1] ? 1: 0);
17 }
18 rank = nr;
19 if (rank[sa[n - 1]] === n - 1) break; // rank all different → done
20 }
21 return sa;
22}
original stringbanana
binary lifting length k1
sa[1,3,5,0,2,4]
1 / 6
Complexity and tradeoffs
Time: O(n log^2 n). Space: O(n). Comparison sorting in each doubling round gives this bound; radix ranking can reach O(n log n).
Invariant: After round k, rank order is exactly lexicographic order for the first 2 to the power k characters of every suffix.
Where it fits
Suffix arrays support substring search, repeated-substring analysis, and compressed text indexes with less pointer overhead than suffix trees.