Amir and Farach (1991) and Amir et al. (to appear) recently initiated
the study of the dynamic dictionary pattern matching problem. The dict
ionary D contains a set of patterns that can change over time by inser
tion and deletion of individual patterns. The user may also present a
text string and ask to search for all occurrences of any patterns in t
he text. For the static dictionary problem, Aho and Corasick (1975) ga
ve a strategy based on a failure function automaton that takes O(\D\lo
g\SIGMA\) time to build a dictionary of size Absolute value of D and s
earches a text T in time O(\T\log\SIGMA\+tocc), where tocc, is the tot
al number of pattern occurrences in the text. Amir et al. (to appear)
used an automaton based on suffix trees to solve the dynamic problem.
Their method can insert or delete a pattern P in time O(\P\log\D\) and
can search a text in time O((\T\+tocc)log\D\). We show that the same
bounds can be achieved using a framework based on failure functions. W
e then show that our approach also allows us to achieve faster search
times at the expense of the update times; for constant k, we can achie
ve linear O(\T\(k + log\SIGMA\)+k tocc) search time with an update tim
e of O(k\P\\D\1/k). This is advantageous if the search texts are much
larger than the dictionary or searches are more frequent than updates.
Finally, we show how to build the initial dictionary in O(\D\log\SIGM
A\) time, regardless of what combination of search and update times is
used.