Improved dynamic text indexing

In the dynamic text indexing problem, a text string has to be maintained un der string insertions and deletions in order to answer on-line queries abou t arbitrary pattern occurrences. By means of some new techniques and data s tructures, 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 t akes 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 t he current text takes O(s log(s + n)) time, (C) 1999 Academic Press.