On updating suffix tree labels

We investigate the problem of maintaining the arc labels in the suffixtree data structure when it undergoes string insertions and deletions. In current literature, this problem is solved either by a simple accounting strategy to obtain amortized bounds or by a periodical suffix tree reconstruction to obtain worst-case bounds (according to the global rebuilding technique). Unfortunately, the former approach is simple and space-efficient at the cost of attaining amortized bounds for the single update; the latter is space-consuming in practice because it needs to keep two extra suffix tree copies. In this paper, we obtain a simple real-time algorithm that achieves worst-case bounds and only requires small additional space (i.e., a bi-directional pointer per suffix tree label). We analyze it by introducing a combinatorial coloring problem on the suffix tree arcs.