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.