DYNAMIC TEXT INDEXING UNDER STRING UPDATES

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.