Aho Corasick algorithm

lastmod 2018-08-17created 2014-09-161 edits

The Aho–Corasick algorithm (Aho–Corasick string matching algorithm) is a matching algorithm for a set of patterns devised by Alfred V. Aho and Margaret J. Corasick. Matching algorithms that search for a single pattern have been shown, through several algorithms such as KMP, to run in linear time. However, running such algorithms over a set of patterns slows them down in proportion to the number of patterns. That is, they have a time complexity of O(m + zn). (m: total length of all patterns, z: number of patterns, n: text size) With the Aho-Corasick algorithm, however, a set of patterns can be searched in time linear in the pattern length and the text, with a time complexity of O(m + n + k). (k: number of pattern occurrences in the text) To implement the Aho-Corasick algorithm, the Keyword Tree, Failure link, and Output link data structures must be used.

Favorite site

• Wikipedia (en) on the Aho-Corasick algorithm
• Set Matching and Aho–Corasick Algorith ¹

References