|
The Aho-Corasick algorithm is a string searching algorithm discovered by Alfred V. Aho and Margaret J. Corasick. It is a kind of dictionary-matching algorithms that locates elements of a finite set of patterns (the "dictionary") within an input text.
Informally, the algorithm constructs a finite automaton first and then applies that automaton to the input text. When the pattern dictionary is known in advance (e.g. a computer virus database), the construction of the automaton can be performed once off-line and the compiled automaton stored for later use.
The Aho-Corasick algorithm forms the basis of the Unix command fgrep.
Sources
|
