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.