|
|||||
|
|
Construction of Aho Corasick automaton in linear time for integer alphabets |
|
| Authors: | Shiri Dori Gad M. Landau |
| Affiliation: | a Department of Computer Science, University of Haifa, Mount Carmel, Haifa 31905, Israel b Department of Computer and Information Science, Polytechnic University, Six MetroTech Center, Brooklyn, NY 11201-3840, USA |
| Abstract: | We present a new simple algorithm that constructs an Aho Corasick automaton for a set of patterns, P, of total length n, in O(n) time and space for integer alphabets. Processing a text of size m over an alphabet Σ with the automaton costs O(mlog|Σ|+k), where there are k occurrences of patterns in the text.A new, efficient implementation of nodes in the Aho Corasick automaton is introduced, which works for suffix trees as well. |
| Keywords: | Design of algorithms String matching Suffix tree Suffix array |
| 本文献已被 ScienceDirect 等数据库收录！ | |