Aho–Corasick string matching algorithm

The Aho - Corasick algorithm is an algorithm based on the search strings and was developed by Alfred V. Aho and Margaret J. Corasick 1975.

The algorithm is a kind of dictionary Comparison, which compares a finite number of known patterns with input text. Simply put, the algorithm builds a finite state machine and compares it with the input text. If the signature is known in advance (for example, an anti -virus database ), then the installation may take place before the start of the off-line program and can be stored for later use.

The Aho - Corasick algorithm is fgrep the base of the UNIX commands, the Snort IDS and the WAF ModSecurity.


  • Search algorithm