Improved dynamic text indexing

In the dynamic text indexing problem, a text string has to be maintained under string insertions and deletions in order to answer on-line queries about arbitrary pattern occurrences. By means of some new techniques and data structures, we achieve improved worst-case bounds. We show that finding all pocc occurrences of a pattern of length p in the current text of length n takes O(p + pocc + upd log p + log n) time, where upd is the number of text uptakes performed so far; inserting or deleting a string of length s from the current text takes O(s log(s + n)) time, (C) 1999 Academic Press.