Dynamic dictionary matching

✍ Scribed by Amihood Amir; Martin Farach; Zvi Galil; Raffaele Giancarlo; Kunsoo Park

• Book ID: 104147818
• Publisher: Elsevier Science
• Year: 1994
• Tongue: English
• Weight: 818 KB
• Volume: 49
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1016/s0022-0000(05)80047-9

✦ Synopsis

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 O 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~[ ). ( 2) delete(p, D~_ 2).

Delete pattern p[1, m] from the dictionary Di_ 2. D~ is the dictionary after the operation. The time complexity is O(m log [Di_ t I). (3) search(t, D~). Search text t[1, n] for all occurrences of the patterns of dictionary D i. The time complexity is O((n + tocc) log [Di] ), where tocc is the total number of occurences of patterns in the text.