DYNAMIC DICTIONARY MATCHING WITH FAILURE FUNCTIONS

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.