[1] It is a kind of dictionary-matching algorithm that locates elements of a finite set of strings (the "dictionary") within an input text.

Informally, the algorithm constructs a finite-state machine that resembles a trie with additional links between the various internal nodes.

These extra internal links allow fast transitions between failed string matches (e.g. a search for cart in a trie that does not contain cart, but contains art, and thus would fail at the node prefixed by car), to other branches of the trie that share a common suffix (e.g., in the previous case, a branch for attribute might be the best lateral transition).

In this case, its run time is linear in the length of the input plus the number of matched entries.

The Aho—Corasick string-matching algorithm formed the basis of the original Unix command fgrep.

The blue arcs can be computed in linear time by performing a breadth-first search [potential suffix node will always be at lower level] starting from the root.

When the algorithm reaches a node, it outputs all the dictionary entries that end at the current character position in the input text.