Lingo

Suffix Array Builder

Build the suffix array by doubling and watch the ranks settle.

Input string

Each suffix is sorted by doubling the compared prefix length: 1, 2, 4, 8, …

Suffix array for "banana"
 0  a
 1  ana
 2  anana
 3  banana
 4  na
 5  nana

Compare 2^1 = 2-character prefixes and re-rank.

6Length
2Rounds
YesSorted
12 cellsSpace