Aho-Corasick algorithm

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

• Alfred V. Aho and Margaret J. Corasick. Efficient string matching: An aid to bibliographic search. Communications of the ACM 18(6):333–340, June 1975. Further details and full text at the ACM Digital Library site