 Aho-Corasick algorithm

The Aho-Corasick algorithm reports occurrences of a finite collection of nonempty pattern strings in one string. It builds an Aho-Corasick automaton from their trie. Each scanned character extends the current state; when no edge matches, failure links find a shorter matching suffix. Report the current terminal pattern string and the terminal ancestors reached through output links.^[ref]

The state represents the longest suffix of the scanned text that is a prefix of some pattern string. This invariant explains correctness: a match ending now is exactly a terminal suffix represented by that state or a failure link ancestor. It also reports overlaps. With pattern strings ab, bab, bc, scanning babc reports ab and bab at position three, then bc at position four.

For a fixed-size alphabet, completed transitions and output links give $O(M+n+z)$ total time, where $M$ is total pattern string length, $n$ text length and $z$ the number of reported occurrences. The $z$ term is unavoidable when listing every match. Store terminal output links instead of copying every inherited match list: copied suffix lists can greatly enlarge preprocessing.