Algorithms on strings, trees, and sequences

TLDR

Weiner first demonstrated linear‑time construction of suffix trees, highlighting its historical significance and distinct technical ideas. The paper aims to present two linear‑time suffix‑tree construction methods—Ukkonen’s and Weiner’s—focusing first on Ukkonen’s approach for readers who prefer a single method. The authors detail both Ukkonen’s and Weiner’s linear‑time construction algorithms, noting that the latter can be understood independently of the former with only a brief shared section. Ukkonen’s method is as fast as Weiner’s but consumes far less memory and is easier to understand, making it the preferred choice for most suffix‑tree construction needs.

Abstract

Linear-Time Construction of Suffix Trees We will present two methods for constructing suffix trees in detail, Ukkonen’s method and Weiner’s method. Weiner was the first to show that suffix trees can be built in linear time, and his method is presented both for its historical importance and for some different technical ideas that it contains. However, lJkkonen’s method is equally fast and uses far less space (i.e., memory) in practice than Weiner’s method Hence Ukkonen is the method of choice for most problems requiring the construction of a suffix tree. We also believe that Ukkonen’s method is easier to understand. Therefore, it will be presented first A reader who wishes to study only one method is advised to concentrate on it. However, our development of Weiner’s method does not depend on understanding Ukkonen’s algorithm, and the two algorithms can be read independently (with one small shared section noted in the description of Weiner’s method).