Name
Abstract | ||
|---|---|---|
Given a set of pattern strings called a dictionary and a text string, dictionary matching is the problem to find the occurrences of the patterns on the text. Dynamic dictionary matching is dictionary matching where patterns may dynamically be inserted into and deleted from the dictionary. The problem is called semi-dynamic dictionary matching when we only consider the insertion. An AC-automaton is a data structure which enables us to solve dictionary matching in O(d log sigma) preprocessing time and O(n log sigma) matching time, where d denotes the total length of the patterns in the dictionary, n denotes the length of the text, and sigma denotes the alphabet size. In this paper we propose an efficient algorithm that dynamically updates an AC automaton for insertion of a new pattern by using a directed acyclic word graph. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1007/978-3-319-46049-9_11 | Lecture Notes in Computer Science |
Keywords | Field | DocType |
Semi-dynamic dictionary matching,AC-automaton,DAWG | Data structure,Combinatorics,K-SVD,Computer science,Automaton,Algorithm,Preprocessor,Sigma,Directed acyclic word graph,Alphabet | Conference |
Volume | ISSN | Citations |
9954 | 0302-9743 | 1 |
PageRank | References | Authors |
0.36 | 7 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Diptarama | 1 | 4 | 1.85 |
| Ryo Yoshinaka | 2 | 172 | 26.19 |
| Ayumi Shinohara | 3 | 936 | 88.28 |