DC3 (Skew) Algorithm

Purpose: Build a suffix array in $O(n)$ time. Kärkkäinen and Sanders (2003) — the first linear-time construction simple enough to fit on a page, and a much gentler read than SA-IS or Farach.

The Idea (“difference cover mod 3”)

Split the positions by index mod 3:

• $S_{12}$ = positions $i\equiv 1,2(\mathrm{mod}3)$ — two thirds of them;
• $S_0$ = positions $i\equiv 0(\mathrm{mod}3)$ — one third.

1. Recurse on $S_{12}$. Form triples (s[i], s[i+1], s[i+2]) for $i\in S_{12}$, radix-sort and name them. Concatenate the names of the $\equiv 1$ positions and then the $\equiv 2$ positions into a string of length $2n/3$, and recursively compute its suffix array. That yields the correct order of all $S_{12}$ suffixes.
2. Sort $S_0$ cheaply. A suffix at position $i\equiv 0$ is s[i] followed by the suffix at $i+1$, which is in $S_{12}$ and therefore already ranked. So sort $S_0$ by the pair (character, known rank) with one radix sort — $O(n)$, no recursion.
3. Merge. Comparing an $S_0$ suffix with an $S_{12}$ suffix takes $O(1)$: strip one or two characters until both indices land in $S_{12}$, where ranks are known. That is exactly why $\{1,2\}$ works as a difference cover mod 3 — any two positions can be aligned into the recursed set within two steps.

Complexity

$T(n)=T(2n/3)+O(n)\Rightarrow T(n)=O(n).$

• Time: $O(n)$
• Space: $O(n)$, though with a larger constant than SA-IS

DC3 vs the alternatives

Method	Time	Memory constant	Implementation difficulty
Prefix doubling (KMR) + sort	$O(n{\log }^{2}n)$	small	easy
Prefix doubling + radix sort	$O(n\log n)$	small	moderate
DC3 / skew	$O(n)$	medium	moderate — ~60 lines
SA-IS	$O(n)$	small	hard — ~90 lines

What to actually use

$O(n\log n)$ prefix doubling handles $n\le 10^6$ comfortably and is far easier to write correctly at 2 a.m. Keep DC3 or SA-IS in your template library for the rare problem with $n\ge 10^7$.

Generalisation: difference covers

$\{1,2\}$ is a difference cover modulo 3: for every $d\in \{0,1,2\}$ there exist $x,y$ in the set with $x-y\equiv d$. That property is exactly what makes step 3 constant-time. The same construction works modulo any $v$ with a difference cover of size $O(\sqrt{v})$ — DC$v$ trades a bigger recursion base for less memory, and DC7 or DC13 are used in memory-constrained implementations.

Variants / Use Cases

• Kasai — pair with any SA construction for the LCP array in $O(n)$
• Suffix array — the topic page with applications
• Difference cover sampling — also used for $O(1)$ longest-common-extension queries in sublinear space
• SA-IS — the faster linear-time alternative used by real libraries