visual-cs / suffix array

Prefix doubling, rank pairs, and lexicographic order in one animated view.

← All Visualizations

Build a suffix array phase by phase.

Watch the prefix-doubling algorithm re-rank all suffixes as the compared prefix length grows from 1 to 2, 4, and beyond. Each step exposes the rank pair (rank[i], rank[i + k]) used to sort suffixes without comparing full strings.

Algorithm
Prefix Doubling
Sort by 2-part ranks, then compress equal pairs into the same rank.
Time
O(n log² n)
Classic implementation: log n phases, each with a sort.
Output
Suffix Array
Sorted starting indices of all suffixes in lexicographic order.
Use Cases
Search, LCP, BWT
A base structure for fast substring work and compressed text indexing.
5×
Ready

Enter a string, preferably ending with a unique sentinel like $, then start the animation.

Length
0
Phase
0
Focus k
1
Distinct ranks
0

String and Active Suffixes

Each card anchors one suffix start position.

Rank Table

The current phase sorts suffixes by (rank[i], rank[i + k]).

# Index Suffix Rank Pair New Rank

Phase Timeline

Auto-play and step mode use the same discrete snapshots.

Final Arrays

The suffix array is the sorted list of starting indices. LCP comes from Kasai's scan.

Suffix Array
LCP Array