| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 428441 | Information Processing Letters | 2006 | 7 Pages |
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
