This paper generalizes the dynamic text indexing problem, introduced i
n [15], to insertion and deletion of strings. The problem is to quickl
y answer on-line queries about the occurrences of arbitrary pattern st
rings in a text that may change due to insertion or deletion of string
s from it. To treat strings as atomic objects, we provide new sequenti
al techniques and related data structures, which combine the suffix tr
ee with the naming technique used in parallel computation on strings.
We also introduce a geometric interpretation of the problem of finding
the occurrences of a pattern in a given substring of the text. As a r
esult, the algorithm allows the insertion in the text of a string S in
O(\S\ log(n + \S\)) amortized time, and the deletion from the text of
a string S in O(\S\ log n) amortized time, where n is the length of t
he current text. A pattern search requires O(p log p + upd (root log n
+ log p) + pocc) worst-case time, where p is the length of the patter
n and pocc is the number of its occurrences in the current text, obtai
ned after the execution of upd update operations. This solution requir
es O(n(2) log n) space, which is not initialized. We also provide a te
chnique to reduce the space to O(n log n), yielding a solution that re
quires O((p + upd) log p root log n + pocc) query time in the worst-ca
se, O(\S\ log(3/2)(\S\ + n)) amortized time to insert a string S in, a
nd O(\S\ log(3/2)n) amortized time to delete a string S from the curre
nt text. Furthermore, we use our techniques to solve the novel on-line
dynamic tree matching problem that requires the on-line detection of
the occurrences of an arbitrary subtree in a forest of ordered labeled
trees. The forest may change due to insertion or deletion of subtrees
or by renaming of some nodes. Such a problem is solved by a simple re
duction to the dynamic text indexing problem. (C) 1997 Academic Press.