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, Di−1). Insert pattern p[1, m] into the dictionary Di−1. Di is the dictionary after the operation. The time complexity is O(m log |Di|). (2) delete(p, Di−1). Delete pattern p[1, m] from the dictionary Di−1. Di is the dictionary after the operation. The time complexity is O(m log |Di−1|). (3) search(t, Di). Search text t[1, n] for all occurrences of the patterns of dictionary Di. The time complexity is O((n + tocc) log |Di|), where tocc is the total number of occurences of patterns in the text.