Farach's Suffix Tree Algorithm

Purpose: Build a suffix tree in $O(n)$ time for an integer alphabet — that is, with no $\log \sigma$ or $\sigma$ factor anywhere. Farach (1997) closed the last gap left by Weiner, McCreight and Ukkonen, all of which pay for the alphabet.

The Idea: odd/even divide and conquer

1. Odd tree. Pair up adjacent characters into $\lceil n/2\rceil$ symbols, radix-sort and rename them, and recurse on the half-length string. Decoding the result gives the suffix tree of all suffixes starting at odd positions.
2. Even tree. Derive the even-position suffix tree from the odd one in $O(n)$: an even suffix is one character plus an odd suffix, whose rank is already known — one radix sort and a tree construction.
3. Merge. Combine the odd and even trees into the full suffix tree in $O(n)$.

$T(n)=T(n/2)+O(n)=O(n).$

The recursion and the first two steps are routine. The merge is the hard part: naively comparing an odd and an even suffix takes unbounded time, so Farach performs an “over-merge” that may produce incorrect internal nodes, then corrects them using the structure of the two input trees and a clever amortized argument.

Complexity

• Time: $O(n)$ for any alphabet that can be sorted in linear time (integers in $[0,n^{O(1)}]$)
• Space: $O(n)$

Why it matters

Before Farach, “linear-time suffix tree” always carried a footnote about the alphabet. Farach’s result is what makes the statement unconditional, and the odd/even recursion he introduced was directly the inspiration for:

• DC3 / skew — the same recurse-on-a-subset-then-merge structure, with thirds instead of halves and a far simpler merge;
• SA-IS — induced sorting, which replaces the merge entirely with two linear scans.

Both are dramatically easier to implement, which is why nobody writes Farach’s algorithm directly. It is the theoretical parent of the practical constructions.

The lineage

Farach 1997  (odd/even D&C, integer alphabet, hard merge)
      |
      +--> Kärkkäinen-Sanders 2003  (DC3: thirds, easy merge)
      |
      +--> Ko-Aluru / Nong-Zhang-Chan  (induced sorting -> SA-IS)

Variants / Use Cases

• DC3 — implementable version of the same idea, for suffix arrays
• SA-IS — the fastest practical linear construction
• Farach-Colton and Bender — the same Farach, a different famous result: $O(1)$ RMQ and LCA
• Suffix Tree — what the structure gives you