TY - JOUR
T1 - Dynamic dictionary matching
AU - Amir, Amihood
AU - Farach, Martin
AU - Galil, Zvi
AU - Giancarlo, Raffaele
AU - Park, Kunsoo
N1 - Funding Information:
* Partially supported by NSF Grant IRI-9013055 and CCR-9223699. t Supported by DIMACS under NSF Contract STC-8809648. * Partially supported by NSF Grant CCR-90-14605. § On leave from University of Palermo, Italy.
PY - 1994/10
Y1 - 1994/10
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0028516157&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0028516157&partnerID=8YFLogxK
U2 - 10.1016/S0022-0000(05)80047-9
DO - 10.1016/S0022-0000(05)80047-9
M3 - Article
AN - SCOPUS:0028516157
SN - 0022-0000
VL - 49
SP - 208
EP - 222
JO - Journal of Computer and System Sciences
JF - Journal of Computer and System Sciences
IS - 2
ER -