Text indexing is a fundamentally important problem in information retrieval.
An text indexing data structure
enables finding all occurances of a pattern in the input text.
The main data structure for text indexing problem, the suffix tree,
allows fast searching in the text; however it is inherently static
in the sense that if the text is modified,
the suffix tree has to be built from scratch.
In this talk we consider the dynamic text indexing problem,
where modifications to the text in the form of insertions and deletions
are permitted.
The only existing data structure for dynmamic text indexing
is the border tree of Gu, Farach and Beigel. A border tree allows
``basic'' modifications in the form
of deletions and insertions of a single character,
in time logarithmic with the size of the
text. However, the searches in the border tree
are asymptotically slower than that in the suffix tree.
In this paper, we introduce a novel data structure for dynamic
text indexing. Our approach
combines the strengths of the border tree and the suffix tree:
it enables fast searches, and fast ``basic'' modifications.
It also allows ``complex'' modifications in the form of insertions and
deletions of substrings of more than one characters at once.