ON UPDATING SUFFIX TREE LABELS

We investigate the problem of maintaining the are labels in the suffix tree data structure (Gusfield et al., 1992; Amir et al., 1994) when i t undergoes string insertions and deletions. In current literature, th is problem is solved either by a simple accounting strategy to obtain amortized bounds (Fiala and Green, 1989; Larson, 1996) or by a periodi cal suffix tree reconstruction to obtain worst-case bounds (according to the global rebuilding technique in Overmars, 1983). Unfortunately, the former approach is simple and space efficient at the cost of attai ning amortized bounds for the single update; the latter is space consu ming, in practice, because it needs to keep two extra suffix tree copi es. In this paper, we obtain a simple realtime algorithm that achieves worst-case bounds and only requires small additional space (i.e., a b i-directional pointer per suffix tree label). We analyze it by introdu cing a combinatorial coloring problem on the suffix tree arcs. (C) 199 8 - Elsevier Science B.V. All rights reserved.