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 D₀ 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 occurences of patterns in the text.