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.
Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-45.ps