Forty Years of Suffix Trees

Alberto Apostolico (1) , Maxime Crochemore (2) , Martín Farach-Colton (3) , Zvi Galil (4) , S. Muthukrishnan (5)

1 Department of Computer Science [Purdue]
2 Informatics
3 RU - Rutgers, The State University of New Jersey [New Brunswick]
4 GATECH - College of Computing
5 Google Inc.

This paper reviews the first 40 years in the life of suffix trees, their many incarnations, and their applications. The paper is non-technical but assumes some familiarity with the structures and constructions discussed. It is not meant to be exhaustive. It is meant to be a tribute to a ubiquitous tool of string matching — the suffix tree and its variants — and one of the most persistent subjects of study in the theory of algorithms.

Mots clés: suffix; factor automaton; suffix automaton; FM-index; array; pattern matching; string searching; bi-tree; suffix tree; dawg; wavelet tree; suf-; fix tree

Domaines: Algorithme et structure de données [cs.DS]

Alberto Apostolico, Maxime Crochemore, Martín Farach-Colton, Zvi Galil, S. Muthukrishnan. Forty Years of Suffix Trees. Communications of the ACM, 2016, 59 (4), pp.66-73. ⟨10.1145/2810036⟩. ⟨hal-01830856⟩