Authors: Ming Gu, Martin Farach and Richard Beigel
ABSTRACT
Text indexing is one of the fundamental problems of string matching.
Indeed, the suffix tree, the central data structure of string
matching, was developed as an efficient static text indexer. The text
indexing problem is that of building a data structure on a text which
allows the occurrences of patterns to be quickly looked up.
All previous text indexing schemes have been static in the sense that
if the text is modified, the data structure must be rebuilt from
scratch. In this paper, we present a first dynamic data structure and
algorithms for the On-line Dynamic Text Indexing problem. Our
algorithms are based on a novel data structure, the border tree, which
exploits string periodicities.
DIMACS Home Page