StringsString Algorithms

Suffix Array (prefix doubling + LCP)

Sort all suffixes of a string by index; with the LCP array it answers substring search, distinct-substring counts and longest-repeat queries.

Learn Suffix Array →

Text | pattern — Lowercase letters: text of 3-12 characters, then a pipe, then a pattern no longer than the text — e.g. "banana | ana"

i	suffix	rank[i]	rank[i+k]	key	lcp
0	banana$	·	·	·	·
1	anana$	·	·	·	·
2	nana$	·	·	·	·
3	ana$	·	·	·	·
4	na$	·	·	·	·
5	a$	·	·	·	·
6	$	·	·	·	·

suffixes, unsorted

sa[0] = 0 banana$sa[1] = 1 anana$sa[2] = 2 nana$sa[3] = 3 ana$sa[4] = 4 na$sa[5] = 5 a$sa[6] = 6 $

1/24A suffix array is the sorted order of all 7 suffixes of "banana$". The appended "$" is smaller than every letter, so no suffix is a prefix of another and the order is total. Sorting them directly costs O(n² log n) because each comparison is O(n) — the trick is to sort by rank instead of by text.

Cell being computedValue it is read fromSettledSearch windowMatching block

PseudocodeLearn Suffix Array →

1s = text + "$"                                  # terminal sorts before every letter
2rank[i] = order of s[i];  k = 1
3while ranks are not all distinct:
4  key[i] = (rank[i], i+k < n ? rank[i+k] : -1)  # rank of the first 2k characters
5  sort suffixes by key;  equal keys keep equal ranks
6  k *= 2                                        # each round doubles the compared prefix
7sa = the sorted order;  lcp[j] = |common prefix of sa[j-1], sa[j]|
8lo = first suffix with prefix >= p;  hi = first suffix with prefix > p
9occurrences of p = sa[lo .. hi-1]               # a contiguous block, because sa is sorted

Variables

textbanana

terminalbanana$

Complexity

best O(n log n)

avg O(n log n)

worst O(n log² n)

space O(n)

Speed