DC3 Suffix Array
Skew Suffix Array Sort (DC3) DC3, also called skew algorithm, builds a suffix array in linear time by splitting suffix positions into residue classes modulo 3 and recursively sorting a subset. It reduces the full suffix ordering problem into a smaller problem, then merges results using rank comparisons. Problem Given a string $T$ of length $n$, construct its suffix array: $$ SA[0 \dots n-1] $$ such that all suffixes are...