Aho-Corasick

(algorithm)

Definition: A multiple string matching algorithm that constructs a finite state machine from a pattern (list of keywords), then uses the machine to locate all occurrences of the keywords in a body of text.

Generalization (I am a kind of ...)
string matching.

Note: Construction of the machine takes time proportional to the sum of the lengths of the keywords. The machine is used to process the text string in a single pass. The number of transitions made by the machine is independent of the number of keywords.

Author: VO

Implementation

Bruce Watson's SPARE Parts, a string pattern recognition toolkit (C++).

More information

Alfred V. Aho and Margaret J. Corasick, Efficient string matching: an aid to bibliographic search, CACM, 18(6):333-340, June 1975.

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.

Entry modified Thu May 5 09:41:49 2005.
HTML page formatted Wed Oct 26 09:47:09 2005.

Cite this as:
Vadim Okun, "Aho-Corasick", from Dictionary of Algorithms and Data Structures, Paul E. Black, ed., NIST.
http://www.nist.gov/dads/HTML/ahoCorasick.html