A suffix array is a deceptively simple idea with outsized power: take every suffix of a string, sort them lexicographically, and store just their starting positions. That sorted order lets you binary-search for any substring in O(m log n), find the longest repeated substring, and much more — all in a compact integer array, a fraction of the memory a suffix tree needs. Pair it with the LCP array — the length of the shared prefix between each pair of neighbours — and repeated patterns fall right out. Sort the suffixes and watch the shared prefixes light up.
O(n log n) construction · O(m log n) substring search · a compact rival to the suffix tree
suffix
The substring from position i to the end. "banana" has 6 suffixes.
suffix array
The starting positions of all suffixes, sorted by the suffixes lexicographically.
LCP array
For each adjacent pair in sorted order, the length of their longest common prefix.
substring search
A pattern occurs iff it is a prefix of some suffix — binary-searchable in the array.
suffix-array.js — sort the suffixes
Ready
The string’s suffixes, sorted lexicographically. Each row shows a suffix, its start index, and the LCP — how many leading characters it shares with the row above. Step to reveal the sorted order.
6
suffixes
0
placed
–
longest repeat
How it works
A suffix array is just an array of integers, yet it answers substring queries almost as well as a full suffix tree. The key observation for search: a pattern P occurs in the text exactly when P is a prefix of at least one suffix. Since the suffixes are sorted, all suffixes starting with P form a contiguous block — so you find them by binary search, in O(m log n). The LCP array adds the other half: the longest common prefix of two adjacent sorted suffixes tells you the longest substring repeated at those two positions, so the maximum LCP value is the length of the longest repeated substring. Naively sorting suffixes is O(n² log n), but classic algorithms build the array in O(n log n) or even O(n).
1
List every suffix
For a string of length n there are n suffixes, one starting at each position. "banana" gives banana, anana, nana, ana, na, a.
2
Sort them lexicographically
Sort the suffixes in dictionary order. The suffix array is the list of their starting positions in this sorted order — a compact integer array.
3
Build the LCP array
For each adjacent pair in the sorted list, record the length of their longest common prefix. The maximum LCP is the longest repeated substring of the text.
✓
Query fast
To find a pattern, binary-search the sorted suffixes: matches form a contiguous block. With the LCP array you also get repeats, distinct substrings, and more — all from one small array.
Build
O(n log n)
Search
O(m log n)
Space
O(n) ints
vs suffix tree
far smaller
The code
# suffix array + LCP (simple O(n^2 log n) build; real ones are O(n log n))def suffix_array(s):
return sorted(range(len(s)), key=lambda i: s[i:]) # sort by suffixdef lcp_array(s, sa):
lcp = [0] * len(sa)
for k in range(1, len(sa)):
a, b = s[sa[k-1]:], s[sa[k]:]
j = 0
while j < len(a) and j < len(b) and a[j] == b[j]: j += 1
lcp[k] = j # shared prefix lengthreturn lcp # max(lcp) = length of the longest repeated substring
Quick check
1. What exactly does a suffix array store?
It stores just the integer starting positions, ordered so that the suffixes they point to are in sorted (dictionary) order. That compactness is its advantage over a suffix tree.
2. How do you search for a pattern using a suffix array?
A pattern P occurs exactly when P is a prefix of some suffix. Because suffixes are sorted, all suffixes starting with P are contiguous, so binary search finds the block in O(m log n).
3. What does the maximum value in the LCP array tell you?
Adjacent sorted suffixes share the longest prefixes, and an LCP of length L between two suffixes means a substring of length L repeats at both positions. So the maximum LCP is the longest repeated substring.
FAQ
What is a suffix array?
An array of the starting positions of all suffixes of a string, sorted so the suffixes are in lexicographic order. It supports fast substring search (binary search) and, with the LCP array, repeated-substring and other queries — using only O(n) integers, far less than a suffix tree.
What is the LCP array?
It stores, for each adjacent pair of sorted suffixes, the length of their longest shared prefix. It supercharges the suffix array: the maximum LCP is the longest repeated substring, and LCP values enable counting distinct substrings and occurrences. Kasai’s algorithm builds it in O(n).
How does a suffix array compare to a suffix tree?
A suffix tree answers more queries optimally but uses much more memory (many pointers) and is fiddly. A suffix array plus LCP array gives most of the same power — search, repeats, distinct substrings — in a compact, cache-friendly integer array. The suffix array is usually preferred in practice.
How fast can a suffix array be built?
Naive string-sorting is O(n² log n). Prefix-doubling (Manber–Myers) is O(n log n), and DC3/skew and SA-IS are O(n). SA-IS is what most high-performance libraries use — linear time and fast in practice.
SOLVE IT YOURSELF
Solve it: sort every suffix without comparing them
Sorting a string’s suffixes naively costs O(n² log n), because each comparison can scan the whole string. Sort by rank pairs and double the length each round, and it drops to O(n log² n). Python or TypeScript.
YOUR TASK
Implement suffix_array(s): return the starting indices of all suffixes of s in lexicographic order. "banana" gives [5, 3, 1, 0, 4, 2].
HINTS — 6 IDEAS
Round 0: rank each position by its own character. Now every suffix is sorted by its first 1 character.
Round k: sort by the pair(rank[i], rank[i+k]). Because both halves are already correctly ranked for length k, that pair sorts them for length 2k.
Use a sentinel like −1 when i + k runs off the end — a shorter suffix must sort before a longer one that shares its prefix.
Re-rank after each sort, giving equal pairs the same rank. That is what lets ties keep resolving in later rounds.
Stop when every rank is distinct — the order is final and further doubling changes nothing.
Lengths go 1, 2, 4, 8 …, so there are only log n rounds, each dominated by one sort.