DYNAMIC DICTIONARY MATCHING

We consider the dynamic dictionary matching problem. We are given a set of pattern strings (the dictionary) that can change over time; that is, we can insert a new pattern into the dictionary or delete a pattern from it. Moreover, given a text string, we must be able to find all occurrences of any pattern of the dictionary in the text. Let D0 be the empty dictionary. We present an algorithm that performs any sequence of the following operations in the given time bounds: (1) insert (p, D(i-1). Insert pattern p[1, m] into the dictionary D(i-1). D(i) is the dictionary after the operation. The time complexity is O(m log \D(i)\). (2) delete(p, D(i-1)). Delete pattern p[1, m] from the dictionary D(i-1). D(i) is the dictionary after the operation. The time complexity is O(m log \D(i-1)\). (3) search(t, D(i)). Search text t[1, n] for all occurrences of the patterns of dictionary D(i). The time complexity is O(n + tocc) log \D(i)\), where tocc is the total number of occurrences of patterns in the text. (C) 1994 Academic Press, Inc.