OPTIMAL ONLINE SEARCH AND SUBLINEAR TIME UPDATE IN STRING-MATCHING

This paper investigates the problem of searching on-line for the occur rences (occ) of an arbitrary pattern of length p in a text of length n subjected to some updates after its preprocessing. Each text update c onsists of inserting or deleting an arbitrary string of length y. We p resent the first dynamic algorithm that achieves optimal query time, i .e., Theta(p + occ), sublinear time per update, i.e., O(root n + y), a nd optimal space, i.e., Theta(n), in the worst case. As a result, our algorithm obtains the same query time and space usage of suffix trees [McCreight, J. Assoc. Comput. Mach., 23 (1976),pp. 262-272] while impr oving their O(n + y) update performance.