Suffix array
A suffix array lists every suffix of a text, the piece from each position to the end, in alphabetical order. It stores only the start positions. Because every substring is the start of some suffix, and the suffixes are sorted, finding any word in the text becomes a binary search.
banana
Sort every suffix of "banana", the word from each position to the end, alphabetically.
1function suffixArray(s) {2 const sa = [...Array(s.length).keys()];3 for (let i = 1; i < sa.length; i++) {4 for (let j = i; j > 0 && s.slice(sa[j]) < s.slice(sa[j - 1]); j--) {5 [sa[j], sa[j - 1]] = [sa[j - 1], sa[j]];6 }7 }8 return sa;9}Keys: Space play or pause, ← → step. The URL always points at the frame you are on.
What it costs
| Case | Time | When |
|---|---|---|
| best | n | already in order, as for abcde, with short comparisons |
| average | n³ | as shown: n² comparisons of suffixes up to n letters long |
| worst | n³ | a library sort brings it to n² log n; real builders reach n log n |
| space | n | one start position per suffix |
Where it breaks
- This build is the slow, clear way. Insertion sort with letter-by-letter comparisons shows every move but costs about n³. Real tools use prefix doubling or SA-IS to build the array in n log n or even n, for texts with millions of letters.
- A shorter suffix comes first on a tie. Pick aaaaa: every suffix is a prefix of the longer ones, so they sort by length, shortest first. That is what the comparison does when one suffix runs out of letters.
- Searching with it. Pick banana: the suffixes starting "ana" sit next to each other in the sorted order, at positions 3 and 1. A binary search finds that block, and its size is how many times "ana" occurs.